algorithm - 降低排序算法中的大 O 复杂度

Question

几周前我认识了 big-O 并试图掌握它，但是尽管有很多关于计算时间复杂度的 Material ，但我似乎无法找到如何使算法更高效。

我一直在练习 Codility 中的演示挑战:

Write a function that, given an array A of N integers, returns the smallest >positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
The given array can have integers between -1 million and 1 million.

我从一个蛮力算法开始:

public int solution(int[] A)
        {
            for ( int number = 1; number < 1000000; number ++)
            {
                if (doesContain(A, number)){}
                else return i;
            }
            return 0;
        }

这通过了所有正确性测试，但性能得分较低，因为运行时间远远超过限制，时间复杂度为 O(N**2)。

然后我尝试将数组放入数组列表中，这减少了 big-O，因为每个对象只被“触摸”一次，而且我可以使用 .Contains，它比迭代更有效(不确定这是不是真的；我只是排序记得在某个地方读过它)。

public int solution(int[] A)
    {
        ArrayList myArr = new ArrayList();
        for (int i=0; i<A.Length; i++)
        {
            myArr.Add(A[i]);
        }
        for ( int i = 1; i < 1000000; i++)
        {
            if (myArr.Contains(i)){}
            else return i;
        }
        return 0;
    }

唉，时间复杂度仍然是 O(N**2)，我找不到如何减少时间的解释。

我知道我不应该使用蛮力，但似乎想不出任何其他方法...任何人都可以解释如何使该算法更高效？

Answer 1

这是一个典型的面试问题。忘记排序；这是一个检测问题，O(n + m) n 元素和 m 的最大值(作为常量给出) .

boolean found[1000000] = False  /// set all elements to false

for i in A    // check all items in the input array
    if i > 0
        found[i] = True

for i in (0, 1000000)
    if not found[i]
        print "Smallest missing number is", i