# 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])
}
```

![暴力解法](/files/-Mfm0jxOf5H0fIGK6-Wu)

> 作为优秀的程序员，虽然可以这么解，但是不应该。虽然从结果看，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
}
```

![辅助空间快速排序](/files/-Mfm0jxQPgh4HVNfwbkS)

#### 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])
}
```

![原地快排](/files/-Mfm0jxR-Sj3qKtlAyw-)

**原地快速排序**

```
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()
}
```

![优先队列](/files/-Mfm0jxUnnD50evv5DkU)

### 四、 逻辑冒泡

* 创建固定容量的容器
* 遍历元素
* 存满后冒泡排序
* 继续插入到头
* 遍历直到遇到大于等于自己的就停止
* 移除最后一个元素

```
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
}
```

![优先队列](/files/DPmAoBaqHBPha0Rj3KYS)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/40.-zui-xiao-dekge-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.