java - 如何在不使用集合的情况下从 Java 中的给定数组中删除重复元素

Question

我有一个这样的数组元素:

int arr[] = {1,1,2,2,3,3,4,4};

我想从中删除重复的元素。在网上搜索，了解到ArrayUtil类。你能告诉我它的用法吗 - 这就是我如何在输出中获得这样的数组:

arr[] = {1,2,3,4};

Answer 1

这是 Element Distinctness Problem 的下一步，在此线程中进行了彻底讨论:Find duplicates in an array ，包括问题的下限(如果不涉及哈希集，就不能比 O(nlogn) 做得更好)。

如果您不愿意使用散列集来检查您已经看到的所有元素，最好的办法是对数组进行排序，然后迭代它 - 所有重复的元素将彼此相邻。

public static int[] justUniques(int[] arr) { 
    if (arr == null || arr.length == 0) return arr;
    Arrays.sort(arr);
    int n = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i-1]) n++;
    }
    int[] res = new int[n];
    res[0] = arr[0];
    n = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[i-1]) res[n++] = arr[i];
    }
    return res;

}

请注意，上面的一个简单变体也可以就地完成，无需创建新数组。

这个解决方案是 O(nlogn)，因此是最优的。如果您不愿意使用 Arrays.sort() 算法，您可以实现自己的排序算法(这很容易)。

另一个提出类似问题但有额外限制的相关主题:Removing the duplicates from an array without disturbing the order of elements without using Sets