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

Question

我有这样的数组元素:

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

我想从中删除重复的元素.在互联网上搜索并了解了ArrayUtil类.你可以通过告诉它的用法来帮助我 - 这就是我如何在输出中获得这样的数组:

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

Answer 1

这是Element Distinctness问题的下一步,在这个线程中对此进行了详细讨论:在数组中查找重复项,包括问题的下限(不能没有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().

另一个相关的线程,它提出了类似的问题和一个额外的限制:从数组中删除重复项而不会在不使用集合的情况下干扰元素的顺序

Answer 2

public int[] removeDuplicates(int[] arr) {
    int[] res = new int[arr.length];
    int index = 0;
    for (int num : arr) {
        if (res.indexOf(num) == -1)
            res[index++] = num;
    }
    return res;
}

这是一个次优的解决方案，但是它不需要对数组进行任何排序。我创建一个新数组，迭代原始数组中的项目，并将这些项目添加到新数组（如果它们尚不存在）。