PermCheck codility.O(N)时间复杂度

Question

嗨我有PermCheck codility的这个解决方案.以下是包含以下问题的链接:https://codility.com/demo/results/demo73YNCU-8FK/

我得到了100%,但我的时间复杂度为O(N*log(N))或O(N).我怎么能使这个代码O(N)？你能简单介绍一下代码O(N)的原因吗？谢谢.

这里代码为快捷方式:

    Array.Sort(A);
    if(A[0] == 1 && A.Length == 1) return 1;
    if(A[0] != 1) return 0;

    int n = 0;
    for(int i = 0; i < A.Length; i++)
    {    
        if(i < A.Length - 1)
        {
            if(A[i+1] == A[i] + 1)
            {
                n += 1;
            }
            else 
            {
                return 0;   
            }
        }

    }
    return 1;

Answer 1

创建一个与输入N相同大小的bool数组,并将所有元素保留为默认的false值.循环遍历输入的每个元素X. 如果X大于N则返回false.如果array [N-1]为true,则返回false.否则将数组[N-1]设置为true.重复.这是O(N).

说明:首先,如果你有一个排列,那么你需要元素1..N,但如果任何元素大于N,那么肯定会缺少一些元素.其次,如果一个元素出现两次,这是一个问题,这就是为什么我们创建bool数组来记住已经看过的元素.