共计 2961 个字符，预计需要花费 8 分钟才能阅读完成。
第一题 色彩分类
题目
解题思路
代码
// 三指针
func sortColors(nums []int) {
// 0 的右边界
left := 0
// 2 的左边界
right := len(nums) - 1
// 指向以后数字
index := 0
for index <= right {if nums[index] == 0 {
// 如果是 0，就往前面移
swap(nums, left, index)
left++
index++
} else if nums[index] == 1 {index++} else if nums[index] == 2 {
// 如果是 2 就往后面移
swap(nums, right, index)
right--
}
}
}
// 替换数组中的两个数字
func swap(nums []int, i int, j int) {nums[i], nums[j]= nums[j],nums[i]
}后果如下
复杂度剖析
复杂度剖析
工夫复杂度：O(n)，其中 n 是数组 nums 的长度，index 指针遍历 0 和 1 元素的长度，最坏后果为数组长度
空间复杂度：O(1)。三个指针，常数级别的空间复杂度
第二题 前 K 个高频元素
题目
解题思路
哈希表存储次数
代码
func topKFrequent(nums []int, k int) []int {m:=make(map[int]int)
var res []int
for _,n:=range nums{m[n]++
}
for i:=0;i<k;i++ {res=append(res,0)
f:=0
for n, v := range m {
if v > f {res[i]=n
f=v
}
}
m[res[i]]=-1
}
return res
}
用时太长
持续优化
堆
这里引入堆的概念
代码
func topKFrequent(nums []int, k int) []int {occurrences := map[int]int{}
for _, num := range nums {occurrences[num]++
}
h := &IHeap{}
heap.Init(h)
for key, value := range occurrences {heap.Push(h, [2]int{key, value})
if h.Len() > k {heap.Pop(h)
}
}
ret := make([]int, k)
for i := 0; i < k; i++ {ret[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return ret
}
type IHeap [][2]int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool {return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(x interface{}) {*h = append(*h, x.([2]int))
}
func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
工夫复杂度：O(Nlogk)，其中 N 为数组的长度。咱们首先遍历原数组，并应用哈希表记录呈现次数，每个元素须要 O(1) 的工夫，共需 O(N) 的工夫。随后，咱们遍历「呈现次数数组」，因为堆的大小至少为 k，因而每次堆操作须要 O(logk) 的工夫，共需 O(Nlogk) 的工夫。二者之和为 O(Nlogk)。
空间复杂度：O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。
执行工夫失去了大幅度优化
基于疾速排序
代码
func topKFrequent(nums []int, k int) []int {occurrences := map[int]int{}
for _, num := range nums {occurrences[num]++
}
values := [][]int{}
for key, value := range occurrences {values = append(values, []int{key, value})
}
ret := make([]int, k)
qsort(values, 0, len(values) - 1, ret, 0, k)
return ret
}
func qsort(values [][]int, start, end int, ret []int, retIndex, k int) {rand.Seed(time.Now().UnixNano())
picked := rand.Int() % (end - start + 1) + start;
values[picked], values[start] = values[start], values[picked]
pivot := values[start][1]
index := start
for i := start + 1; i <= end; i++ {if values[i][1] >= pivot {values[index + 1], values[i] = values[i], values[index + 1]
index++
}
}
values[start], values[index] = values[index], values[start]
if k <= index - start {qsort(values, start, index - 1, ret, retIndex, k)
} else {
for i := start; i <= index; i++ {ret[retIndex] = values[i][0]
retIndex++
}
if k > index - start + 1 {qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1))
}
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
工夫复杂度：O(N^2)，其中 N 为数组的长度。
设解决长度为 N 的数组的工夫复杂度为 f(N)。因为解决的过程包含一次遍历和一次子分支的递归，最好状况下，有 f(N)=O(N)+f(N/2)，依据 主定理，可能失去 f(N)=O(N)。
最坏状况下，每次取的中枢数组的元素都位于数组的两端，工夫复杂度进化为 O(N^2)。但因为咱们在每次递归的开始会先随机选取中枢元素，故呈现最坏状况的概率很低。
均匀状况下，工夫复杂度为 O(N)。
空间复杂度：O(N)。哈希表的大小为 O(N)，用于排序的数组的大小也为 O(N)，疾速排序的空间复杂度最好状况为 O(logN)，最坏状况为 O(N)。
正文完
