小编Sam*_*016的帖子

我最近在一次采访中被要求编写代码以确定整数数组是否包含重复项,因为我自信地告诉他我将迭代元素并将每个元素添加到新数组中(如果数组不包含元素)已经如果它我返回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)的复杂性.有什么想法可以做到这一点？