减少代码的时间复杂度，从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，因为向集合中添加元素的代码必须首先查看它是否已经在集合中

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

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

Answer 2

我认为如果你看一下HashSet的基本工作机制会很有用。 HashSet在内部是一个数组，但是数据访问（例如“检查元素是否存在”）或“添加/删除元素”具有时间复杂度O（1），因为它采用映射机制来映射对象到存储它的索引。例如，如果你有一个HashSet和一个整数并且你做一个hashSet.contains(integer)，程序将首先取整数并计算它的哈希码，然后使用映射机制（不同于实现到实现）来查找索引存储它。假设我们的哈希码为4，并使用最简单的映射机制映射到索引4，然后我们将检查基础数组的第4个元素是否为空。如果是的话，hashSet.contains(integer)将返回true，否则false。

Answer 3

提供的代码的复杂性是O（N ^ 2）。但是，下面给出的代码是复杂度O（N）。它使用HashSet，它需要插入和搜索O（1）操作。

    public static boolean findIfArrayHasDuplicates(int[] array){

            HashSet<Integer> set = new HashSet<Integer>();
            set.add(array[0]);

            for (int index = 1; index < array.length; index++) {
                    if(!set.add(array[index]))
                            return true;
            }

            return false;
     }