在给定的排列中找到缺失的元素

Question

首先，一些背景知识：

我正在研究 the Codility lessons 之一，尽管这很容易解决，但从逻辑上讲，在性能方面并不容易解决。

我已经能够将其归结为：

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: {[=10=]<}).reduce(0) { ( == [=10=] + 1) ?  : [=10=] } + 1
}

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

但我想试试。我正在查看的部分是：

.reduce(0) { ( == [=11=] + 1) ?  : [=11=] }

我想知道我是否可以使比较更有效率。

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

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

是否有比基本的“==”运算符更高效的方法来比较两个正整数是否相等？

顺便说一句：这不是 "do my homework for me" 问题。这是非常合法的，这些 Codility 课程不会给你信用或任何东西。它们只是一个有趣的练习。我想知道如何做到这一点，因为我确定我将来会需要它。

Answer 1

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

您只需生成正确的数组，通过调用 Array(1...A.count+1) 包含 [1..(N + 1)] 范围内的每个整数。然后使用 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) 时达到或不达到对应为止。

在给定的排列中找到缺失的元素

Find the missing element in a given permutation

arrays

reduce

compare

swift