减少代码的时间复杂度,从N*N中查找数组中的重复项

Question

我最近在一次采访中被要求编写代码以确定整数数组是否包含重复项,因为我自信地告诉他我将迭代元素并将每个元素添加到新数组中(如果数组不包含元素)已经如果它我返回true其他返回虚假的复杂性

代码就是这样的

//complexity is N*N
    public static boolean findIfArrayHasDuplicates(int[] array){


        int[] newArr = new int[array.length];
        List<Integer> intList = new ArrayList<Integer>();

        for (int var: array){
            if(intList.contains(var)){
                return true;
            }else{
                intList.add(var);
            }
        }
        return false;
    }   
}

他让我计算我写的代码的时间复杂度

我回答了

N用于迭代循环N(N + 1)/ 2,用于查找元素是否存在于新列表N中以添加列表中的元素

O()表示法中的总N + N + N*N/2 + N/2乘以2并简化为N趋于无穷大,这可以简化为O(N ^ 2)

他继续问我是否有更好的方法我回答将元素添加到集合中并比较大小如果集合的大小小于它包含重复的数组,请问它的复杂程度是什么仍然是O(N ^ 2),因为添加元素的代码必须首先看看它是否已经在集合中.如何使用所需的内存减少O(N ^ 2)的复杂性.有什么想法可以做到这一点？

Answer 1

他继续问我是否有更好的方法我回答将元素添加到集合中并比较大小如果集合的大小小于它包含重复的数组,请问它的复杂程度是什么仍然是NN,因为向集合中添加元素的代码必须首先查看它是否已经在集合中

那是错的.如果要将元素添加到a HashSet,则需要花费预期的O(1)时间来添加每个元素(包括检查元素是否已存在),因为您只需要计算hashCode以找到可能包含元素的bin(取常量)然后,搜索存储在该bin中的元素(这也是预期的恒定时间,假设每个bin中的元素的平均数量由常量绑定).

因此,总的运行时间是O(N),并没有什么可以改进的(你找不到重复的小于O(N)).