40.最小的k个数

题目

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、 暴力解法

先排序，然后直接取。

func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
    if k == 0 { return [] }
    if arr.count <= k { return arr }
    let rearr: [Int] = arr.sorted { $0 <= $1 }
    return Array(rearr[0...k-1])
}

暴力解法

作为优秀的程序员，虽然可以这么解，但是不应该。虽然从结果看，Swift的排序算法效率非常高。

二、 快速排序

func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
    if k == 0 { return [] }
    if arr.count <= k { return arr }
    let result = quickSort(arr)
    return Array(result[0...k-1])
}

2.1 辅助空间

此法较为容易理解

func quickSort<T: Comparable>(_ arr: [T]) -> [T] {
    guard let base = arr.first, arr.count > 1 else {
        return arr
    }
    
    var left: [T] = []
    var right: [T] = []
    var result: [T] = []

    for index in 1..<arr.count {
        let value = arr[index]
        if value < base {
            left.append(value)
        }
        else {
            right.append(value)
        }
    }
        
    result = quickSort(left)
    result.append(base)
    result.append(contentsOf: quickSort(right))
    
    return result
}

辅助空间快速排序

2.2 原地快排

func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
    if k == 0 { return [] }
    if arr.count <= k { return arr }
    var result = arr
    quickSort(&result, 0, arr.count - 1, k)
    return Array(result[0...k-1])
}

原地快排

原地快速排序

func quickSort<T: Comparable>(_ arr: inout [T], _ low: Int, _ high: Int, _ k: Int) {
    let res = partition(&arr, low: low, high: high)
    if res == k {
        return
    }
    else if res > k {
        quickSort2(&arr, low, res-1, k)
    }
    else {
        quickSort2(&arr, res+1, high, k)
    }
}

确定基准元素的下标

func partition<T: Comparable>(_ arr: inout [T], low: Int, high: Int) -> Int {
    let root = arr[high]
    var index = low
    for i in low...high {
        if arr[i] < root {
            if i != index {
                arr.swapAt(i, index)
            }
            index = index+1
        }
    }
    
    if high != index {
        arr.swapAt(high, index)
    }
    return index
}

三、 优先队列

• 什么是优先队列

  • 按照一定条件给定的条件

  • 每次加入元素都会进行排序

  • 优先级最高的元素上浮到首位

本题我们可以：

• 限制队列元素数量

• 更大的元素具有更高优先级

• 当队列达到k值后

• 移除最高优先级的元素

• 最后剩下的就是最小的k个元素了

首先我们需要实现一下优先队列

优先队列实现

public struct SwiftPriorityQueue<Element> {
    private let _hasHigherPriority: (Element, Element) -> Bool
    private let _isEqual: (Element, Element) -> Bool

    private var _elements = [Element]()

    public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
        _hasHigherPriority = hasHigherPriority
        _isEqual = isEqual
    }

    public mutating func enqueue(_ element: Element) {
        _elements.append(element)
        bubbleToHigherPriority(_elements.count - 1)
    }

    public func peek() -> Element? {
        return _elements.first
    }
    
    public func array() -> [Element] {
        return _elements
    }

    public var isEmpty: Bool {
        return _elements.count == 0
    }
    
    public var count: Int {
        return _elements.count
    }

    public mutating func dequeue() -> Element? {
        guard let front = peek() else {
            return nil
        }

        removeAt(0)

        return front
    }

    public mutating func remove(_ element: Element) {
        for i in 0 ..< _elements.count {
            if _isEqual(_elements[i], element) {
                removeAt(i)
                return
            }
        }
    }

    private mutating func removeAt(_ index: Int) {
        let removingLast = index == _elements.count - 1
        if !removingLast {
            _elements.swapAt(index, _elements.count - 1)
        }

        _ = _elements.popLast()

        if !removingLast {
            bubbleToHigherPriority(index)
            bubbleToLowerPriority(index)
        }
    }

    private mutating func bubbleToHigherPriority(_ initialUnbalancedIndex: Int) {
        precondition(initialUnbalancedIndex >= 0)
        precondition(initialUnbalancedIndex < _elements.count)

        var unbalancedIndex = initialUnbalancedIndex

        while unbalancedIndex > 0 {
            let parentIndex = (unbalancedIndex - 1) / 2
            guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
            _elements.swapAt(unbalancedIndex, parentIndex)
            unbalancedIndex = parentIndex
        }
    }

    private mutating func bubbleToLowerPriority(_ initialUnbalancedIndex: Int) {
        precondition(initialUnbalancedIndex >= 0)
        precondition(initialUnbalancedIndex < _elements.count)

        var unbalancedIndex = initialUnbalancedIndex
        while true {
            let leftChildIndex = unbalancedIndex * 2 + 1
            let rightChildIndex = unbalancedIndex * 2 + 2

            var highestPriorityIndex = unbalancedIndex

            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
                highestPriorityIndex = leftChildIndex
            }

            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
                highestPriorityIndex = rightChildIndex
            }

            guard highestPriorityIndex != unbalancedIndex else { break }
            _elements.swapAt(highestPriorityIndex, unbalancedIndex)

            unbalancedIndex = highestPriorityIndex
        }
    }
}

extension SwiftPriorityQueue : CustomDebugStringConvertible {
    public var debugDescription: String {
        return _elements.debugDescription
    }
}

题解

func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
    var stack = SwiftPriorityQueue<Int>(hasHigherPriority: { $0 > $1 }, isEqual: { $0 == $1 })
    
    arr.forEach { item in
        stack.enqueue(item)
        if stack.count > k {
            stack.dequeue()// 最高优先级的出列（最大的出去）
        }
    }
    
    return stack.array()
}

优先队列

四、 逻辑冒泡

• 创建固定容量的容器

• 遍历元素

• 存满后冒泡排序

• 继续插入到头

• 遍历直到遇到大于等于自己的就停止

• 移除最后一个元素

func getLeastNumbers5(_ arr: [Int], _ k: Int) -> [Int] {
    var result: [Int] = []
    
    guard k > 0 else {
        return result
    }
    
    arr.forEach { item in
        if result.count == k, let min = result.first {
            
            if item <= min {
                result.insert(item, at: 0)
                result.removeLast()
            }
            else {
                result.insert(item, at: 0)
                
                for i in 0..<(result.count - 1) {
                    if result[i] > result[i+1] {
                        result.swapAt(i, i+1)
                    }
                    else {
                        break
                    }
                }
                
                result.removeLast()
            }
        }
        else {
            result.append(item)
            if result.count == k {
                result = result.sorted()
            }
        }
    }
    
    return result
}

优先队列