Java数组高效去重

高效移除数组中重复元素是编程中的一个基本任务。本文探讨了三种不同的Java方法，每种方法在速度和内存使用之间取得了不同的平衡。了解这些权衡对于选择适合您特定应用程序的最佳方法至关重要。

目录

• 使用临时数组
• 使用单独索引
• 使用Arrays.sort()方法
• 方法比较

使用临时数组

这种直接的方法迭代输入数组。每个元素都与一个临时数组进行检查，该临时数组只包含迄今为止遇到的唯一元素。如果在临时数组中找不到元素，则将其添加。虽然易于理解，但其嵌套循环结构导致时间复杂度为O(n²) ，这使得它对于大型数组效率低下。

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesTempArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0]; 
        }

        int[] uniqueArr = new int[arr.length]; 
        int uniqueCount = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < uniqueCount; j++) {
                if (arr[i] == uniqueArr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount); 
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
        int[] uniqueArr = removeDuplicatesTempArray(arr);
        System.out.println("原始数组: " + Arrays.toString(arr));
        System.out.println("移除重复元素后的数组: " + Arrays.toString(uniqueArr));
    }
}

时间复杂度：O(n²)
空间复杂度：O(n)

使用单独索引

此方法通过就地修改原始数组来提高空间效率。它使用单独的索引来跟踪下一个唯一元素的位置。迭代数组，并将唯一元素移动到此索引指示的位置。虽然空间效率高(O(1))，但由于嵌套循环，它的时间复杂度仍然是O(n²)。

public class RemoveDuplicates {

    public static int[] removeDuplicatesIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int index = 1; 
        for (int i = 1; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < index; j++) {
                if (arr[i] == arr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                arr[index++] = arr[i];
            }
        }
        return Arrays.copyOf(arr, index);
    }
    //main 方法与上面相同
}

时间复杂度：O(n²)
空间复杂度：O(1)

使用Arrays.sort()方法

这种方法利用Java内置的排序功能。首先对数组进行排序，将重复元素放在一起。随后对排序后的数组进行单次遍历，识别并仅保留每个元素的第一次出现。时间复杂度由排序算法决定(O(n log n))，对于大型数据集，其性能明显优于以前的方法。

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        Arrays.sort(arr); 
        int[] uniqueArr = new int[arr.length];
        uniqueArr[0] = arr[0]; 
        int uniqueCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount);
    }
    //main 方法与上面相同
}

时间复杂度：O(n log n)
空间复杂度：O(n)

方法比较

方法的选择取决于数据的规模和您的优先级。对于较小的数组，临时数组方法的简单性可能就足够了。对于较大的数组，Arrays.sort()方法的性能提升超过了其略高的空间复杂度。单独索引方法提供了一种空间效率高的解决方案，但其二次时间复杂度使其对于大型数据集不太有吸引力。