java - 整数数组中的重复数字(Java 基础级别)和时间复杂度

Question

我创建了一个整数数组，并使用 Math.random() 用随机数初始化了这个数组。

我试图在不使用 Arraylist 或 Hashset 的情况下打印数组中的重复数字。我的代码(进行中):

public class Test{
    public static final int Length = 20;
    public static void main(String[] args) {

        int a[]= new int[Length];
        for(int i=0; i<a.length; i++){
            a[i]=(int)(Math.random()*Length);
        }
        for(int i=0; i<a.length; i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
        isDuplicate(a);
        System.exit(0);
    }//eof main
    public static void isDuplicate(int a[]){
        System.out.print("Duplicates: ");
        boolean test[] = new boolean[Length];
        for(int i=0; i<test.length; i++){
            test[i]=false;
        }
        for(int i=0; i<a.length; i++){
            if(test[a[i]]==false){
                test[a[i]]=true;
            }
            else
                System.out.print(a[i]+" ");
        }
        System.out.println();
    }//eof isDuplicate
}

示例输出:

    16 15 12 7 0 7 2 14 12 18 1 8 2 15 4 5 6 5 12 7 
Duplicates: 7 12 2 15 5 12 7 

The correct output has to be : 7 12 2 15 5

它工作正常，但是当数组中的数字重复超过两个时，它会打印出一个以上的数字。我该如何解决？另一方面，我试图计算这个算法的时间复杂度，这是 O(n) 吗？

Answer 1

不要使用 boolean 数组，而是使用另一个整数数组，因为你正在填充最多 20 个元素，你可以创建一个大小为 20 的整数数组，每次读取数字时都这样做，假设数组大小为 20 的称为“计数”。

int count[] = new int[Length];
for(int i = 0; i < 20; i++) {
    count[a[i]]++;
}

for(int i = 0; i < 20; i++) {
    if(count[i] > 1)
        System.out.println(i);
}

这将打印出多次出现的数字。