c# - PermCheck 可修改性。 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。如果数组 [N-1] 为真，则返回假。否则将 array[N-1] 设置为 true。重复。这是 O(N)。

解释:首先，如果你有一个排列，那么你需要元素 1..N，但是如果任何元素大于 N，那么肯定会缺少一些元素。其次，如果一个元素出现两次，那就是个问题，这就是我们创建 bool 数组以记住已经出现的元素的原因。