找出给定排列中缺失的元素

Question

首先，一点背景：

我正在学习一门Codibility课程，尽管从逻辑上讲这很容易解决，但从性能上讲，这并不容易解决。

我可以把它归结为：

public func solution(_ A : inout [Int]) -> Int {
let B = A   // Assigning it to a local speeds it up.
return Array<Int>(Set(B)).sorted(by: {$0<$1}).reduce(0) { ($1 == $0 + 1) ? $1 : $0 } + 1
}

然而，这只是一个WEE有点太慢了。我想主要原因是reduce遍历了数组的所有元素，尽管答案可能很早。我可能无法加快速度。

但我想试试。我看到的部分是：

.reduce(0) { ($1 == $0 + 1) ? $1 : $0 }

我想知道我是否能使这种比较更有效率。

我必须检查$1是否等于$0+1。我无法避免这种比较。

三元运算符实际上并不比if子句快，但看起来更酷；)。

有没有比基本的"=="运算符更高性能的方法来比较两个正整数的等价性？

BTW：这不是一个"为我做作业"的问题。这是非常合法的，这些密码课程不会给你任何荣誉或任何东西。它们只是一种有趣的锻炼。我想知道如何做到这一点，因为我相信我将来会需要它。

Answer 1

使用@TNguyen在评论中建议的解决方案，以下代码的正确性和性能都达到了100%。

您只需要通过调用Array(1...A.count+1)来生成正确的数组，该数组包含范围[1..(N + 1)]中的每个Integer。然后使用reduce(0,+)求和它的元素，最后减去输入数组A的元素之和。两个和之间的差给出了缺失的元素。

public func solution(_ A : inout [Int]) -> Int {
return Array(1...A.count+1).reduce(0,+)-A.reduce(0,+)
}

一个更快的解决方案是对第一个和使用数学公式1+2+...+n=n(n-1)/2。

public func solution(_ A : inout [Int]) -> Int {
return (A.count+1)*(A.count+2)/2-A.reduce(0,+)
}

Answer 2

使用其他概念在python中获得100%的分数：

def solution(A):
Index=0;
while (Index<len(A)):
while((A[Index]-1) != Index and A[Index]<=len(A)):
Tmp=A[Index]; #Permut
A[Index]=A[Tmp-1];
A[Tmp-1]=Tmp;
Index+=1;
Index=0;
while Index<len(A):
if((A[Index]-1) != Index) :
return Index+1;
else:
Index+=1;
return len(A)+1;  
pass

背后的想法是，对于给定的排列，除了缺失的元素外，每个元素a[Index]-1都应该与Index匹配。然后排列阵列的元素，直到当A[Index]>len(A)时实现或未实现对应。