java - 面试时问的时间复杂度问题

Question

int[] a = {3,5,4,3,2,2,1};

        System.out.println("Duplicate elements are: ");

        for(int i=0; i<a.length; i++) {
            for(int j = i+1; j<a.length; j++) {
                if(a[i]==a[j]  && i!=j){
                    System.out.println(a[j] + " ");
                }
            }
        }

这段代码时间复杂度是O(n^2)，面试官让我把它改成O(n)。我们怎么能做到这一点？

标签： javaalgorithmloopsdata-structurestime-complexity

Answer 1

这是一种满足O(n)要求的解决方案，即使用HashSet-AHashSet将不接受重复值，因此您只需要一个循环，即如果要求允许使用声明的HashSet：

int[] a = {3,5,4,3,2,2,1};
// Create a set 
Set<Integer> set = new HashSet<Integer>();
//Create a set for storing duplicates
Set<Integer> setDupes = new HashSet<Integer>();

System.out.println("Duplicate elements are: ");

//loop the array once 
for (int num : a) 
{ 
     if (set.add(num) == false) 
     { 
        // your duplicate element
        if(setDupes.add(num) == true) 
           System.out.println(num + " ");
     } 
}