PermCheck协同性.O(N)时间复杂性

本文关键字：时间复杂性 PermCheck | 更新日期: 2023-09-27 18:29:57

嗨，我有这个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;

PermCheck协同性.O(N)时间复杂性

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

解释：首先，如果你有一个置换，那么你需要元素1..N，但如果任何元素大于N，那么肯定会缺少一些元素。其次，如果一个元素出现两次，那就是一个问题，这就是为什么我们创建bool数组来记住已经看到的元素。

我的python解决方案（不需要额外的库，看起来像python，别人也不难理解）：

    def solution(A): return 1 if len(set(A)) == len(A) == sorted(A)[-1] else 0

可以简化为：

    def solution(A):
        if len(set(A)) == len(A):
            if len(A) == sorted(A)[-1]:
                return 1
        return 0

我检查了两个时刻：

1:数组中集合的长度（集合不能有重复项）等于初始数组的长度

传递的数组（无重复）：[1,3,2,4]，[4,3,2,5]

阵列失败：[1,1,2,4]，[5,6,6,1]

2：初始数组的长度等于排序数组中的最后一个元素

传递的数组：[1，2，3，4]：长度等于最后一个元素=>返回1

阵列失败：[2，3，4，5]：长度不等于最后一个元素=>返回0

如果A包含0或负元素，则此代码不起作用，但根据任务详细信息：数组A的每个元素都是[1..1000000000]范围内的整数。

Codibility显示100%和O（N）或O（N*log（N））

尝试使其成为O（N）（由fejesjoco建议）：

def solution(A):
        array_length = len(A)
        seen_values = [False] * array_length
        for x in A:
            if x > array_length:
                return 0
            else:
                if seen_values[x - 1]:
                    return 0
                else:
                    seen_values[x - 1] = True
        return 1

Codibility result 100%检测到的时间复杂度：O（N）或O（N*log（N））

两种代码显示出相同的结果和时间复杂性。也许共同性不能正确评估它？

这是我的100/100答案：

与@fejesjoco 理念相同

https://codility.com/demo/results/demoNR485D-33P/

您可以将int更改为long以获得性能。

    public int solution(int[] A)
    {
        // idea: add to set,dictionary. Count the size and compare to N.
        // dedupe data when needed. 
        var set = new HashSet<int>();
        var max = int.MinValue;
        foreach (var item in A)
        {
            if (set.Contains(item)) return 0;
            set.Add(item);
            if (item > max) max = item;
        }
        return set.Count == max ? 1 : 0;
    }

这是我的解决方案，正确性和性能都达到了100%。

def解决方案（A）：阵列强度=len（A）

if (arraylength > 100000):
    raise ValueError("Out of bound range")    
arr = sorted(A)
for i in range(arraylength):
    if (arr[i] != i+1):
        return 0
return 1

我知道这个问题很久以前就被问过了，但它仍然活跃在协同性中。

可能的解决方案：

public int solution(int[] A)
{
    return (Enumerable.Range(1, A.Length).Except(A).Count() == 0) ? 1 : 0;
}

根据fejesjoco的建议，

Boolean[] bln = new Boolean[A.Length];       
for (int i = 0; i < A.Length; i++)
{
    if (A[i] > A.Length) // more than array length
        return 0;
    if (bln[A[i]-1]) // same value twice
        return 0;
    bln[A[i]-1] = true;
}
return 1;

这是我的解决方案，它的得分为100%。不要忘记添加"；使用System.Linq"；。

int distinctLength = A.Distinct().ToArray().Length;
// The array length should equal to the distinct array length which is also the maximum value in array A.
if (A.Length == distinctLength && distinctLength == A.Max()) { return 1; }
return 0;

Swift Solution 100%

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    let sorted = A.sorted()
    for (index, value) in sorted.enumerated() {
        if index+1 != value {
            return 0
        }
    }
    return 1
}
相关文章：