java - 在不使用集合的情况下从数组中删除重复项而不扰乱元素的顺序

Question

我需要一个java代码，它可以从数组中删除重复项，而不改变元素的顺序，也不使用集合或排序技术。

例如:如果输入数组为 {23,1,5,4,2,23,6,2,4}那么输出应该是 {23,1,5,4,2,6}

Answer 1

您可以使用 O(1) 额外空间在 O(n^2) 时间内完成此操作。

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讨论它。