java - 不使用 Util 类从数组中删除重复项

Question

请先阅读问题，然后再将其标记为重复

我编写了以下代码来从数组中删除重复项，而不使用 Util 类，但现在我陷入困境

public class RemoveDups{
    public static void main(String[] args) {
        int[] a = { 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 3, 1, 4, 52, 1, 45, };

        int temp;
        for (int i : a) {
            for (int j = 0; j < a.length - 1; j++) {
                if (a[j] > a[j + 1]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        a = removeDups(a);
        for (int i : a) {
            System.out.println(i);
        }

    }

    private static int[] removeDups(int[] a) {
        int[] result = new int[a.length];
        int j = 0;
        for (int i : a) {
            if (!isExist(result, i)) {
                result[j++] = i;
            }
        }

        return result;
    }

    private static boolean isExist(int[] result, int i) {
        for (int j : result) {
            if (j == i) {
                return true;
            }
        }
        return false;
    }

}

现在输出是

1
2
3
4
5
6
45
52
0
0
0
0
0
0
0
0
0
0

我的问题是

1. 我的代码在 0 的情况下不起作用
2. 我无法理解对数组进行排序如何减少执行时间
3. 是否有任何方法可以在不使用 Util 类的情况下从数组中删除元素我知道一种将数组转换为列表然后删除的方法，但为此我们也需要 Util 类，有什么方法可以自己实现。

Answer 1

由于您处理的数字仅限于一个小范围，因此您可以通过简单的“计数排序”来删除重复项:在类似集合的数据结构中标记您找到的数字，然后检查该数据结构。 boolean 值数组工作得很好，为了减少内存使用，您可以创建一个基本的位集或哈希表。如果 n 是数组中元素的数量，m 是范围的大小，则该算法的复杂度为 O(n+m)。

private static int[] removeDups(int[] a, int maxA) {
    boolean[] present = new boolean[maxA+1];
    int countUnique = 0;
    for (int i : a) {
        if (!present[i]) {
            countUnique++;
            present[i] = true;
        }
    }

    int[] result = new int[countUnique];
    int j = 0;
    for (int i=0; i<present.length; i++) {
        if (present[i]) result[j++] = i;
    }

    return result;
}

I am not able to understand how sorting an array can reduce time of execution

在排序数组中，您可以在一次扫描中检测重复项，花费 O(n) 时间。由于排序比检查每一对更快 - 时间复杂度为 O(n log n) ，而时间复杂度为 O(n²) - 对数组进行排序比使用朴素算法更快。