arrays - k-最大元素优化 Swift 3.0

Question

如何优化 Swift 3.0 中找到 k 个最大元素的算法？

 func largestElement(arr: [Int], k: Int) -> Int? {


    let length = arr.count

    if k > 0 && k <= length {

        for k in 0..<length {
          print(k)
        }

        let sorted = arr.sorted() 

        return sorted[length - k]


    } else {
        return nil
    }

}

var arrayOfIntegers = [1, 6, 3, 9, 13, 15]
print(largestElement(arr: arrayOfIntegers, k: 5))

消除 sorted() 函数的最佳方法是什么？

Answer 1

Quickselect是一个众所周知的查找数组中第 k 个最小元素的算法O(N) 的平均复杂度。

这是该算法在 Swift 3 中的可能实现。它使用与维基百科文章中的代码示例相同的方法，但是用迭代而不是递归。枢轴元素也是没有移到第二个分区的前面。这样可以节省一些交换操作，但更新时需要额外检查下限。

extension Array where Element: Comparable {

    func kSmallest(_ k: Int) -> Element {
        precondition(1 <= k && k <= count, "k must be in the range 1...count")

        var a = self // A mutable copy.
        var low = startIndex
        var high = endIndex

        while high - low > 1 {

            // Choose random pivot element:
            let pivotElement = a[low + Int(arc4random_uniform(UInt32(high - low)))]

            // Partition elements such that:
            //   a[i] <  pivotElement    for low <= i < pivotIndex,
            //   a[i] >= pivotElement    for pivotIndex <= i < high.
            var pivotIndex = low
            while a[pivotIndex] < pivotElement {
                pivotIndex += 1
            }
            for i in pivotIndex+1 ..< high {
                if a[i] < pivotElement {
                    swap(&a[pivotIndex], &a[i])
                    pivotIndex += 1
                }
            }

            if k <= pivotIndex {
                // k-smallest element is in the first partition:
                high = pivotIndex
            } else if k == pivotIndex + 1 {
                // Pivot element is the k-smallest:
                return pivotElement
            } else {
                // k-smallest element is in the second partition
                // (but not the pivot element)
                low = pivotIndex
                if a[low] == pivotElement {
                    low += 1
                }
            }
        }

        // Only single candidate left:
        return a[low]
    }

    func kLargest(_ k: Int) -> Element {
        return kSmallest(count + 1 - k)
    }
}

例子:

let a = [2, 2, 3, 3, 1, 1, 4, 4]
for i in  1...a.count {
    let l = a.kLargest(i)
    print(l)
}
// 4 4 3 3 2 2 1 1