在 swift 中的排序数组中查找最大数量的连续整数的最佳方法，最好不要使用 for 循环

Question

给定一个整数数组，例如 let array = [1, 3, 4, 7, 8, 9, 12, 14, 15] 最好在不使用 for-in 循环的情况下找到最大数量的连续整数的最佳方法是什么。如果我们将此数组传递给函数，它将 return 3 因为 '7, 8, 9' 是连续整数的最大数量。

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]

func getMaxConsecutives(from array: [Int]) -> Int {
    var maxCount = 1
    var tempMaxCount = 1
    var currentNumber = array[0]
    for number in array {
        if currentNumber == number - 1 {
            tempMaxCount += 1
            maxCount = tempMaxCount > maxCount ? tempMaxCount : maxCount
            currentNumber = number
        } else {
            tempMaxCount = 1
            currentNumber = number
        }
    }
    return maxCount
}

getMaxConsecutives(from: array)

这按预期工作，但我想要一个更有效的解决方案，而不是 O(n)。感谢任何有创意的回答。

Answer 1

你可以这样做：

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]  
if let maxCount = IndexSet(array).rangeView.max(by: {[=10=].count < .count})?.count {
    print("The largest amount of consecutive integers: \(maxCount)")
    //prints 3
}

Answer 2

我觉得我可以写的更严密一点（基本上是one-liner）：

let array = [1, 3, 4, 7, 8, 9, 12, 14, 15]
let (_,_,result) = array.reduce((-1000,1,0)) {
     == [=10=].0+1 ? (,[=10=].1+1,max([=10=].2,[=10=].1+1)) : (,1,[=10=].2) 
}
print(result) // 3

但是我们仍然在遍历整个数组——所以我们是 O(n)——并且没有办法避免这种情况。毕竟，想想你的眼睛在扫描阵列寻找答案时所做的事情：它扫描整个阵列。

（实现一些节省的一种方法：当我们不在运行中间时，您可以 short-circuit 循环并且到目前为止的最大值运行比什么长数组的剩余部分！但增益可能并不显着。）

在 swift 中的排序数组中查找最大数量的连续整数的最佳方法，最好不要使用 for 循环

Best way to find the largest amount of consecutive integers in a sorted array in swift, preferably not using a for loop

algorithm

big-o

swift