剑指 Offer 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]

❤️4种解法秒杀TopK： 快排 / 堆 / 二叉搜索树 / 计数排序

  1. 解题思路：
  2. 一、用快排最最最高效解决 TopK 问题：
  3. 二、大根堆(前 K 小) / 小根堆（前 K 大),Java中有现成的 PriorityQueue，实现起来最简单：
  4. 三、二叉搜索树也可以 解决 TopK 问题哦
  5. 四、数据范围有限时直接计数排序就行了：
  • 方法一：堆，时间复杂度 O(n_log_k)
  • 方法二：快排变形，（平均）时间复杂度O(n)

方法三：使用排序算法解决最直观，对数组 arr 执行排序，再返回前 k 个元素即可

  1. //修改快排，平均nlogn,最坏On^2 ; 空间平均logn，最坏On
  2. func getLeastNumbers(arr []int, k int) []int {
  3.     if k == 0 {
  4.         return []int{}
  5.     }
  6.     quickSort(arr, 0 , len(arr) - 1)
  8.     return arr[:k]
  9.     //return arr[len(arr)-k:]                //最大k个数
  10. }
  12. func quickSort(nums []int, left, right int) {
  13.     if left > right {
  14.         return
  15.     }
  17.     i, j, base := left, right, nums[left]               //优化点，随机选基准
  19.     for i < j {
  20.         for nums[j] >= base && i < j {
  21.             j--
  22.         }
  23.         for nums[i] <= base && i < j {
  24.             i++
  25.         }
  26.         nums[i], nums[j] = nums[j], nums[i]
  27.     }
  28.     nums[i], nums[left] = nums[left], nums[i]
  30.     quickSort(nums, left, i - 1)
  31.     quickSort(nums, i + 1, right)
  32. }
// 堆排，时间nlogk，空间On；结果同方法三
import "container/heap"
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 大根堆
func getLeastNumbers(arr []int, k int) []int {
    if k==0{return []int{}}
    h := make(IntHeap,k)
    hp:=&h

    copy(h ,IntHeap(arr[:k+1]))
    heap.Init(hp)

    for i:=k;i<len(arr);i++{
        if arr[i]<h[0]{
            heap.Pop(hp)
            heap.Push(hp,arr[i])
        }
    }
    return h
}

方法二： 基于快速排序的数组划分

  • 题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
  • 根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。
  • 根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。 ```go // 基于快排的数组划分，平均时间On，稍微好点;空间平均logn， func getLeastNumbers(arr []int, k int) []int { if k == 0 {
      return []int{}
    } start, end := 0, len(arr) - 1 index := partition2(arr, start, end) for index != k - 1{
      if index > k - 1{
      end = index - 1
  }else {
      start = index + 1
  }
  index = partition2(arr, start, end)
    } return arr[:k] }

func partition2(nums []int, low, high int) int { key := nums[low] for low < high { for low < high && nums[high] >= key { high— } nums[low] = nums[high] for low < high && nums[low] <= key { low++ } nums[high] = nums[low] } nums[low] = key return low } ``` image.png