Links

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
}
优先队列