刪除數組中的副本而不會影響元素的順序而不使用集合

Question

我需要一個java代碼，它可以從數組中刪除重複項而不改變元素的順序，並且不使用集合或排序技術。

例如： 如果輸入數組是{23,1,5,4,2,23,6,2,4} 然後輸出應爲{23,1,5,4,2,6}

Answer 1

你可以用Ø做到在O(n^2)時間（ 1）額外空間。

public static int[] noSpaceElementDistinctness(int[] arr) { 
    int n = arr.length; 
    for (int i = 0; i < n;i++) { 
     boolean exists = false; 
     for (int j = 0; j < i; j++) { 
      if (arr[i] == arr[j]) { 
       exists = true; 
       break; 
      } 
     } 
     if (exists) { 
      for (int j = i+1; j<n; j++) 
       arr[j-1] = arr[j]; 
     n--; 
     i--; //to iterate the next element, which is now at index i, not i+1. 
     } 
    } 
    for (int i = n; i < arr.length; i++) arr[i] = Integer.MIN_VALUE; //indicates no value 
    return arr; 

} 

---

作爲一個側面說明，元素清晰度問題不是小事有效地解決，因爲它可能從第一眼看上去，這是一個問題，嚴格的下界，你可以做些什麼來解決它有效。 This thread討論它。

Answer 2

創建一個新的ArrayList（）。在舊列表中循環並將值複製到新的值，除非它已經在其中。

順序將會改變，因爲你不會複製所有...

Answer 3

如果使用Java 8簡單的方法是：

int[] array = {23, 1, 5, 4, 2, 23, 6, 2, 4}; 
int[] noDupes = IntStream.of(array).distinct().toArray(); 
System.out.println(Arrays.toString(noDupes)); // [23, 1, 5, 4, 2, 6] 

Answer 4

有幾個選擇 - 一些比其他人更有效：

/** 
* Brute force approach - very inefficient. 
* 
* Finds each duplicate and removes it. 
*/ 
private int[] removeDupesUsingNoExtraMemory(int[] a) { 
    int length = a.length; 
    for (int i = 0; i < length - 1; i++) { 
     for (int j = i + 1; j < length; j++) { 
      if (a[i] == a[j]) { 
       // No point copying if this is the last one. 
       if (j < length - 1) { 
        // Remove a[j]. 
        System.arraycopy(a, j + 1, a, j, length - j - 1); 
       } 
       length -= 1; 
      } 
     } 
    } 
    // Actually it does use extra memory but only to trim the array because Java cannot slice arrays. 
    return Arrays.copyOf(a, length); 
} 

/** 
* A bit more efficient. 
* 
* Copies only non-duplicate ones. 
*/ 
private int[] removeDupesDifferently(int[] a) { 
    int length = a.length; 
    // Copying to the end backwards. 
    int to = length - 1; 
    // Copy backwards so we remove the second duplicate - not the first. 
    for (int i = length - 1; i >= 0; i--) { 
     boolean duplicate = false; 
     for (int j = 0; j < i && !duplicate; j++) { 
      duplicate |= a[i] == a[j]; 
     } 
     if (!duplicate) { 
      a[to--] = a[i]; 
     } 
    } 
    return Arrays.copyOfRange(a, to + 1, a.length); 
} 

/** 
* Most efficient - but uses a `Set`. 
* 
* Builds a `Set` of `seen` values so we don't copy duplicates. 
*/ 
private int[] removeDupesUsingASet(int[] a) { 
    int to = 0; 
    Set<Integer> seen = new HashSet<>(); 
    for (int i = 0; i < a.length - 1; i++) { 
     // Seen it before? 
     if (!seen.contains(a[i])) { 
      a[to++] = a[i]; 
      // Seen that one - don't want to see it again. 
      seen.add(a[i]); 
     } 
    } 
    return Arrays.copyOf(a, to); 
} 

public void test() { 
    System.out.println("removeDupesUsingNoExtraMemory = " + Arrays.toString(removeDupesUsingNoExtraMemory(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4}))); 
    System.out.println("removeDupesDifferently = " + Arrays.toString(removeDupesDifferently(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4}))); 
    System.out.println("removeDupesUsingASet = " + Arrays.toString(removeDupesUsingASet(new int[]{23, 1, 5, 4, 2, 23, 6, 2, 4}))); 
} 

Answer 5

int arr[] = {23,1,5,4,2,6} ; 
    List<Integer> list = new ArrayList<Integer>(); 
    for(int i = 0; i<arr.length; i++) { 
     if (!list.contains(arr[i])) { 
      list.add(arr[i]); 
     } 
    } 

    Iterator it = list.iterator(); 
    while(it.hasNext()){ 
     System.out.println(it.next()); 
    } 

Answer 6

如果您只需要在不修改陣列的情況下打印唯一元素，則可以使用此替代解決方案來完成。排序爲O陣列（N log n）的（合併排序例如），並通過在陣列O（n）的運行只打印有它們的相鄰元件不同的元件，即：

if(arr[i] != arr[i + 1]) { 
    print(arr[i]); 
} 

乾杯！