最小的k个数 - Lab.Lawliet

题目#

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

示例 1：

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

示例 2：

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

限制：

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

来源：力扣（LeetCode）

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

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

一、暴力解法#

先排序，然后直接取。

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

暴力解法

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

二、快速排序#

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

2.1 辅助空间#

此法较为容易理解

1
func quickSort<T: Comparable>(_ arr: [T]) -> [T] {
2
    guard let base = arr.first, arr.count > 1 else {
3
        return arr
4
    }
5

6
    var left: [T] = []
7
    var right: [T] = []
8
    var result: [T] = []
9

10
    for index in 1..<arr.count {
11
        let value = arr[index]
12
        if value < base {
13
            left.append(value)
14
        }
15
        else {
16
            right.append(value)
17
        }
18
    }
19

20
    result = quickSort(left)
21
    result.append(base)
22
    result.append(contentsOf: quickSort(right))
23

24
    return result
25
}

辅助空间快速排序

2.2 原地快排#

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

原地快排

原地快速排序#

1
func quickSort<T: Comparable>(_ arr: inout [T], _ low: Int, _ high: Int, _ k: Int) {
2
    let res = partition(&arr, low: low, high: high)
3
    if res == k {
4
        return
5
    }
6
    else if res > k {
7
        quickSort2(&arr, low, res-1, k)
8
    }
9
    else {
10
        quickSort2(&arr, res+1, high, k)
11
    }
12
}

确定基准元素的下标#

1
func partition<T: Comparable>(_ arr: inout [T], low: Int, high: Int) -> Int {
2
    let root = arr[high]
3
    var index = low
4
    for i in low...high {
5
        if arr[i] < root {
6
            if i != index {
7
                arr.swapAt(i, index)
8
            }
9
            index = index+1
10
        }
11
    }
12

13
    if high != index {
14
        arr.swapAt(high, index)
15
    }
16
    return index
17
}

三、优先队列#

什么是优先队列
- 按照一定条件给定的条件
- 每次加入元素都会进行排序
- 优先级最高的元素上浮到首位

本题我们可以：

限制队列元素数量
更大的元素具有更高优先级
当队列达到k值后
移除最高优先级的元素
最后剩下的就是最小的k个元素了

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

优先队列实现#

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

5
    private var _elements = [Element]()
6

7
    public init(hasHigherPriority: @escaping (Element, Element) -> Bool, isEqual: @escaping (Element, Element) -> Bool) {
8
        _hasHigherPriority = hasHigherPriority
9
        _isEqual = isEqual
10
    }
11

12
    public mutating func enqueue(_ element: Element) {
13
        _elements.append(element)
14
        bubbleToHigherPriority(_elements.count - 1)
15
    }
16

17
    public func peek() -> Element? {
18
        return _elements.first
19
    }
20

21
    public func array() -> [Element] {
22
        return _elements
23
    }
24

25
    public var isEmpty: Bool {
26
        return _elements.count == 0
27
    }
28

29
    public var count: Int {
30
        return _elements.count
31
    }
32

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

38
        removeAt(0)
39

40
        return front
41
    }
42

43
    public mutating func remove(_ element: Element) {
44
        for i in 0 ..< _elements.count {
45
            if _isEqual(_elements[i], element) {
46
                removeAt(i)
47
                return
48
            }
49
        }
50
    }
51

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

58
        _ = _elements.popLast()
59

60
        if !removingLast {
61
            bubbleToHigherPriority(index)
62
            bubbleToLowerPriority(index)
63
        }
64
    }
65

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

70
        var unbalancedIndex = initialUnbalancedIndex
71

72
        while unbalancedIndex > 0 {
73
            let parentIndex = (unbalancedIndex - 1) / 2
74
            guard _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) else { break }
75
            _elements.swapAt(unbalancedIndex, parentIndex)
76
            unbalancedIndex = parentIndex
77
        }
78
    }
79

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

84
        var unbalancedIndex = initialUnbalancedIndex
85
        while true {
86
            let leftChildIndex = unbalancedIndex * 2 + 1
87
            let rightChildIndex = unbalancedIndex * 2 + 2
88

89
            var highestPriorityIndex = unbalancedIndex
90

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

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

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

102
            unbalancedIndex = highestPriorityIndex
103
        }
104
    }
105
}
106

107
extension SwiftPriorityQueue : CustomDebugStringConvertible {
108
    public var debugDescription: String {
109
        return _elements.debugDescription
110
    }
111
}

题解#

1
func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
2
    var stack = SwiftPriorityQueue<Int>(hasHigherPriority: { $0 > $1 }, isEqual: { $0 == $1 })
3

4
    arr.forEach { item in
5
        stack.enqueue(item)
6
        if stack.count > k {
7
            stack.dequeue()// 最高优先级的出列（最大的出去）
8
        }
9
    }
10

11
    return stack.array()
12
}

优先队列

四、逻辑冒泡#

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

1
func getLeastNumbers5(_ arr: [Int], _ k: Int) -> [Int] {
2
    var result: [Int] = []
3

4
    guard k > 0 else {
5
        return result
6
    }
7

8
    arr.forEach { item in
9
        if result.count == k, let min = result.first {
10

11
            if item <= min {
12
                result.insert(item, at: 0)
13
                result.removeLast()
14
            }
15
            else {
16
                result.insert(item, at: 0)
17

18
                for i in 0..<(result.count - 1) {
19
                    if result[i] > result[i+1] {
20
                        result.swapAt(i, i+1)
21
                    }
22
                    else {
23
                        break
24
                    }
25
                }
26

27
                result.removeLast()
28
            }
29
        }
30
        else {
31
            result.append(item)
32
            if result.count == k {
33
                result = result.sorted()
34
            }
35
        }
36
    }
37

38
    return result
39
}

优先队列

题目#

一、 暴力解法#

二、 快速排序#

2.1 辅助空间#

2.2 原地快排#

原地快速排序#

确定基准元素的下标#

三、 优先队列#

优先队列实现#

题解#

四、 逻辑冒泡#

一、暴力解法#

二、快速排序#

三、优先队列#

四、逻辑冒泡#