Java，以 O(n) 时间复杂度从数组中首次复制值

Question

int firstDuplicate(int[] a) {
    Set<Integer> result = new HashSet();
    for(int i=0; i<a.length; i++) {
        if(result.contains(a[i])) {
            return a[i];
        } else {
            result.add(a[i]);
        }
    }
    return -1;
}

上面代码的复杂性是O(n2)因为 for 循环内部包含检查。

如何O(n)在java中实现这一点的复杂性。

ArrayList 的 .contains 实现

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

Answer 1

您提供的实现与类contains(Object)中的方法相对应ArrayList。您使用的方法实际上是HashSet.contains(Object)。

的复杂度HashSet.contains(Object)是O(1)。为了实现这一点，它使用存储值的哈希值来查找所搜索的元素。

万一两个对象共享相同的哈希值，两个元素将存储在列表中的相同哈希值下。这可能是误导您相信成本为 O(n) 的原因HashSet.contains(Object)。虽然有一个列表，但元素几乎均匀分布，因此列表大小趋于1，将O(n)转变为O(1)。