Smallest K LCCI

题目描述

最小K个数：

找出数组中最小的K个数，以任意顺序返回。

示例：

输入：arr = [1, 3, 5, 7, 2, 4, 6, 8], k = 4
输出：[1, 2, 3, 4]

解法

解法一：快排选择思想

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func smallestK(arr []int, k int) []int {
    n := len(arr)
    if n <= k {
        return arr
    }
    slow, fast := 0, 0
    for fast < n-1 {
        if arr[fast] <= arr[n-1] {
            arr[slow], arr[fast] = arr[fast], arr[slow]
            slow++
        }
        fast++
    }
    arr[slow], arr[n-1] = arr[n-1], arr[slow]
    if slow == k || slow+1 == k {
        return arr[:k]
    }
    if slow > k {
        return smallestK(arr[:slow], k)
    }
    ans := append(arr[:slow+1], smallestK(arr[slow+1:], k-slow-1)...)
    return ans
}

解法二：排序选前K个数

代码省略

解法三：堆排序

维护包含k个元素的大顶堆，然后返回即可。代码省略。