面试问题之Top K系列

思路整理:

如图所示

  1. aLjufN
  2. b8s2H2

几种方法讲解

以剑指offer40题为例,求最小的k个数字

方法一:

思路:直接用最快的排序方法排好序后取前k个或者后k个元素即可

时间复杂度:O(n * logn)
空间复杂度:O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func getLeastNumbers(arr []int, k int) []int {
return QuickSort(arr)[:k]
}

func QuickSort(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, low int, high int) {
var pivotkey int
//优化1:尾递归优化
for low < high {
//pivotkey 为枢轴防止的最终下标
pivotkey = partition(nums, low, high)
quickSort(nums, low, pivotkey-1)
low = pivotkey + 1
}
}

func partition(nums []int, low int, high int) int {
//优化2:使用随机数选择划分枢轴
//设置随机数种子
rand.Seed(time.Now().UnixNano())
//选择[0,n)
//rand.Intn(n)
//选择划分元素
dummyIndex := rand.Intn(high-low+1) + low
//将随机选择的元素放置到low位置上,以后便于在高处找到比划分元素小的时候我们可以直接让high赋值给low
swap(nums, low, dummyIndex)
dummyVal := nums[low]
for low < high {
for low < high && dummyVal <= nums[high] {
high--
}
//优化3:我们使用替换而不是交换
//高处找到小的直接赋值给low
nums[low] = nums[high]
for low < high && dummyVal >= nums[low] {
low++
}
//低处找到大的直接赋值给high
nums[high] = nums[low]
}
//最后low == high
nums[low] = dummyVal
return low
}

func swap(nums []int, i int, j int) {
nums[i], nums[j] = nums[j], nums[i]
}

方法二:

思路:冒泡排序每次都会将1个元素放置到最终位置上,我们可以冒泡k趟

时间复杂度:O(k * n)
空间复杂度:O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
func getLeastNumbers(arr []int, k int) []int {
//需要冒泡k次
for i := 1; i <= k; i++ {
//每次从倒数第2个元素开始一直到前面的第i-1个元素,例如第1趟是到第0个(因为每次是和后面的元素进行比较)
for j := len(arr) - 2; j >= i-1; j-- {
if arr[j] > arr[j+1] {
arr[j+1], arr[j] = arr[j], arr[j+1]
}
}
}
return arr[:k]
}

go中的heap实现大根堆与小根堆

小根堆

几个注意点:

  1. 我们使用Less比较的时候决定了大根堆或小根堆
  2. push以及pop需要传入指针,因为涉及到改动。
  3. pop的时候需要删除最后一个,因为我们是append自己模拟进去的
  4. 我们自己用堆加入元素的时候需要使用heap中的方法来加入元素heap.push()和删除元素heap.pop()
  5. 如果我们自己想要查看堆顶,切片中索引为0对应的元素就是堆顶
1
2
3
4
5
minHeap := &MinHeap{}
heap.Init(minHeap)
heap.Push(minHeap, 123)
heap.Push(minHeap, 999)
num := heap.Pop(minHeap) //将会弹出堆顶