leetcode刷题类型（二）- - - 排序类型
- 求解 Kth Element 问题，也就是第 K 个元素的问题
- 求解 TopK Elements 问题，也就是 K 个最小元素的问题
解法：
- 借助快速排序
- 借助最小堆
215 第 K 个元素的问题
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
解法一: 借助快速排序
这类题目可以利用快速排序的partition()进行查找
在一个递增的数组中，第K大的元素的下标是N-K，因此只要数组前N-K个元素有序递增即可。
假设partion()返回元素的位置为j，那么j位置的元素 >= j左侧的元素
- 如果j = N-K，那么j位置元素就是第K大元素
- 如果j < N-K，那么第K大元素在右侧，新的左边界为j+1
- 如果j > N-K，那么第K大元素在左侧，新的右边界为j-1
func findKthLargest(nums []int, k int) int {
rand.Seed(time.Now().UnixNano())
return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}
func quickSelect(arr []int, left, right, target int) int {
j := randomPartition(arr, left, right)
//target即N-K
if j == target {
return arr[j]
} else if j < target { //j < N-K，那么第K大元素在右侧，新的左边界为j+1
return quickSelect(arr, j+1, right, target)
}
return quickSelect(arr, left, j-1, target) //j > N-K，那么第K大元素在左侧，新的右边界为j-1
}
func randomPartition(arr []int, left, right int) int {
//避免partion会退化成O(N)
i := rand.Int() % (right - left + 1) + l // rand Intn生成的是[0,（right-left+1）]的值，所以要加1
arr[i], arr[right] = arr[right], arr[i]
return partition(arr, left, right)
}
func partition(arr []int,left int,right int) int {
i:=left+1 //左指针
j:=right //右指针
//默认与arr[left]为分割，最终比arr[left]小的在其左边，比arr[left]大的在其右边
for true{
for i<right {
if arr[i]>flag { //找比arr[left]大的值，找不到就右移接着找
break
}
i++
}
for j>left { //找比arr[left]小的值，找不到就左移接着找
if arr[j]<flag {
break
}
j--
}
//没有找到
if i>=j {
break
}
//找到了，进行交换
arr[i], arr[j] = arr[j], arr[i]
}
//此时，arr[left]<arr[j]<arr[i]
arr[left], arr[j] = arr[j], arr[left]
return j
}
解法二：借助最小堆
借助最小堆，把所有元素放入最小堆中，然后pop出N-K个元素，这时堆中只剩下K个元素，堆顶元素就是第K大元素。
go中提供了 container/heap 来实现堆，堆中元素的类型需要实现 heap.Interface 这个接口。
最大堆：func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
最小堆：func (h IntHeap) Less(i, j int) bool
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 findKthLargest(nums []int, k int) int {
h := &IntHeap{}
heap.Init(h)
for _,v:=range nums{ //将所有元素放入堆中
heap.Push(h,v)
}
if k < len(nums) {
for i:=0;i<len(nums)-k;i++{ //弹出N-K个元素
heap.Pop(h)
}
}
return heap.Pop(h).(int) //此时的栈顶元素为第K大元素
}
K 个最小元素返回的时候返回数组的[0:N-K]或者堆的N-K到堆中最后一个元素即可
347 出现频率最多的 k 个元素
解法一：借助最大堆
首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值，然后遍历出现次数数组的值，插入最大堆中，堆中弹出的前k个元素即为出现频率最多的 k 个元素。
若只根据出现次数构建最大堆，在获取堆元素后无法知道该出现次数属于哪个元素，所以堆中每个节点不仅需要保存元素出现的次数（count），还需要保存该次数是属于哪个元素（value)。可以将两者放到Item中，以Item作为堆的一个节点。
type Item struct {
value int //存储元素
count int //存储元素出现的次数
}
type IntHeap []*Item //堆中每个节点存储一个Item，包含了元素和元素出现的次数
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].count > h[j].count } //根据元素出现的次数构建最大堆
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.(*Item))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
arr:=[]int{1,1,1,2,2,3}
fmt.Println(topKFrequent(arr,2))
}
func topKFrequent(nums []int, k int) []int {
res := make([]int,k)
m:=make(map[int]int)
for _,v := range nums { //遍历数组统计每个元素出现的次数
m[v]++
}
h:=&IntHeap{}
heap.Init(h)
for value,count := range m {
heap.Push(h,&Item{value,count}) //每一条map的数据作为一个Item入堆
}
for i:=0;i<k;i++ { //堆顶元素为最大值，即出现次数最多，因此弹出的前k个堆顶元素就是出现次数最多的前k个元素
res[i]=heap.Pop(h).(*Item).value //将此时堆顶元素中的value，即最初的数组元素加入返回数组中
}
return res
}
451 根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
和347类似，构建最大堆，根据堆顶元素确定返回字符串中字符的顺序和个数。
type Item struct {
value byte //存储字符
count int //存储字符出现的次数
}
type IntHeap []*Item //堆中每个节点存储一个Item，包含了元素和元素出现的次数
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].count > h[j].count } //根据元素出现的次数构建最大堆
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.(*Item))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func frequencySort(s string) string {
arr:=[]byte(s)
var res []byte
m:=make(map[byte]int)
for _,v := range arr { //遍历数组统计每个元素出现的次数
m[v]++
}
h:=&IntHeap{}
heap.Init(h)
for value,count := range m {
heap.Push(h,&Item{value,count}) //每一条map的数据作为一个Item入堆
}
for h.Len()>0 {
item:=heap.Pop(h).(*Item)
for i:=item.count;i>0;i--{ //弹出栈顶元素，出现了几次就append几次到res数组中
res = append(res,item.value)
}
}
return string(res)
}
75 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
解法一：暴力
统计出数组中 0, 1, 20,1,2 的个数，再根据它们的数量，重写整个数组
解法二：双指针
将数组中所有的0交换到数组的头部
将数组中所有的2交换到数组的尾部
func sortColors(nums []int) {
p0, p2 := 0, len(nums)-1
for i := 0; i <= p2; i++ {
for ; i <= p2 && nums[i] == 2; p2-- { //nums[i]为2时交换到数组尾部
nums[i], nums[p2] = nums[p2], nums[i]
}
if nums[i] == 0 { //交换后nums[i]为0，交换到数组头部
nums[i], nums[p0] = nums[p0], nums[i]
p0++
}
}
}
如有不对，烦请指出，感谢~
参考自：
http://www.cyc2018.xyz/
https://leetcode-cn.com/problems