如何在不使用集合的情况下从Java中的给定数组中删除重复的元素 [英] How can I remove duplicate elements from a given array in java without using collections

问题描述

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

I have an array elements like this:

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

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

I want to remove the duplicate elements from. Searched on the internet and came to know about ArrayUtil class. Could you please help me by telling it's usage - that's how can I get an array like this in output:

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

推荐答案

这是元素区别的下一步问题，在此线程中进行了详细讨论:在数组中查找重复项，包括该问题的下限(没有涉及散列集的O(nlogn)不能做得更好).

This is the next step from Element Distinctness Problem, which is discussed thoroughly in this thread: Find duplicates in an array, including lower bounds for the problem (cannot do better than O(nlogn) without a hash set involved).

如果您不愿意使用哈希集来检查已经看到的所有元素，那么最好的选择是对数组进行排序，然后对其进行迭代-所有重复的元素将彼此相邻.

If you are unwilling to use a hash-set to check out all the elements you have already seen, your best bet is to sort the array, and then iterate it - all duplicate elements will be adjacent to each other.

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;

}

请注意，上述内容的简单变体也可以就地完成，而无需创建新数组.

Note that a simple variation of the above can also do it in-place, without creating a new array.

此解决方案是O(nlogn)，因此是最佳的.如果您不愿意使用Arrays.sort()一种算法，则可以实现自己的排序算法(相当简单).

This solution is O(nlogn), and thus is optimal. You can implement your own sorting algorithm (it's fairly easy) if you are unwilling to use the Arrays.sort() one.

另一个相关的线程，提出类似的问题，但有一个额外的限制:从数组中删除重复项，而无需使用Sets，而不会干扰元素的顺序

Another related thread that asks similar question with an additional restriction: Removing the duplicates from an array without disturbing the order of elements without using Sets

这篇关于如何在不使用集合的情况下从Java中的给定数组中删除重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！