算法技巧--一维数组去重

说明

这段代码的思路是使用两个循环来对数组进行去重操作，并将结果重新封装到一个新的数组中。
整体思路是通过两个循环遍历数组，将重复出现的元素标记为 -1，然后根据标记的情况创建一个新的数组来存储去重后的结果。

代码的时间复杂度为 O(n^2)，其中 n 是输入数组的长度。
外层循环从 0 到 n-2 进行迭代，内层循环从外层循环的下一个元素开始迭代到 n-1。因此，内层循环的迭代次数会逐渐减少。
在最坏情况下，即数组中没有重复元素时，内层循环将完全执行 n-1 + n-2 + ... + 1 = (n-1)n/2 次。这是一个等差数列求和公式。
然而，在内层循环中，当发现重复元素时，会将重复元素标记为 -1，并增加 len 计数器。内层循环在后续迭代中会跳过被标记为 -1 的元素。
因此，当数组中有 k 个重复元素时，内层循环的迭代次数将会减少 k 次。
最后，创建新数组的循环将迭代 n 次，其中 n 是输入数组的长度。

因此，总体来说，该代码的时间复杂度为 O(n^2)。在最坏情况下，即数组中没有重复元素时，时间复杂度为 O(n^2)。在最好情况下，即数组中所有元素都是重复的，时间复杂度为 O(n)。平均情况下，时间复杂度仍然是 O(n^2)。

实现

public static void test (int[] arr){
    int len = 0;        //标记去重的次数
    int newLen = 0;
    int[] newArray;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i+1; j < arr.length; j++) {
            if (arr[i] == -1) {
                continue;
            } else {
                if (arr[i] == arr[j]) {
                    arr[j] = -1;
                    len++;
                }
            }
        }
    }

    //不使用 list 的情况下，用数组重新封装结果
    newArray = new int[arr.length - len];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != -1) {
            newArray[newLen] = arr[i];
            newLen++;
        }
    }
    printResult (newArray);
}

public static void printResult(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

public static void main(String[] args) {
    int[] arr = {1, 4, 6, 4, 3, 5, 5, 0, 9, 8, 2, 4, 3, 8, 9, 7};
    test(arr);
}