LeetCode中级算法-排序和搜索（1）
颜色分类
[题目]
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
[输入1]
nums = [2,0,1][返回1]
[0,1,2][输入2]
nums = [2,0,2,1,1,0][返回2]
[0,0,1,1,2,2][解法1]
使用一个指针，遍历两遍数组，第一遍遍历将数组中所有的0交换到数组的开头，记录一个targetIndex为当前替换到了哪个位置，第二遍遍历的时候，从上一次的targetIndex开始，将数组中所有的1从这个位置开始交换
[代码实现1]
func computeResult(input []int) []int {
// 首先将所有的0交换到最前面
targetIndex, input := _compute(input, 0, 0)
// 然后将1接着targetIndex放置
_, input = _compute(input, 1, targetIndex)
return input
}
func _compute(input []int, target int, targetIndex int) (int, []int) {
for i := 0; i < len(input); i++ {
if input[i] == target {
input[i], input[targetIndex] = input[targetIndex], input[i]
targetIndex++
}
}
return targetIndex, input
}[解法2]
使用两个指针，分别遍历0和2的元素，将0交换到数组的开头位置，将2交换到数组结尾的位置
[代码实现2]
func computeResult2(input []int) []int {
targetStartIndex := 0
targetEndIndex := len(input) - 1
for i := 0; i < len(input); i++ {
if input[i] == 0 {
input[i], input[targetStartIndex] = input[targetStartIndex], input[i]
targetStartIndex++
} else if input[i] == 2 {
input[i], input[targetEndIndex] = input[targetEndIndex], input[i]
targetEndIndex--
}
}
return input
}[代码测试]
package main
import "fmt"
func main() {
//input := []int {2,0,2,1,1,0}
input := []int {2, 0, 1}
result := computeResult(input)
fmt.Println("result:", result)
result2 := computeResult2(input)
fmt.Println("result2:", result2)
}前 K 个高频元素
[题目]
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
[输入1]
nums = [1,1,1,2,2,3], k = 2[返回1]
[1,2][输入2]
nums = [1], k = 1[返回2]
[1][解法]
首先遍历一遍数组，按照key-value存储每个元素出现的次数，key为元素，value是该元素出现的次数，遍历完成之后，建立一个小顶堆，golang中小顶堆的建立可以使用heap.Init，遍历元素出现次数的map，将[key, value]的数组加入到小顶堆中，当小顶堆中元素超过k的时候，就弹出堆顶的元素，直到将整个map遍历完毕
[代码实现]
package main
import (
"container/heap"
"fmt"
)
func main() {
input := []int {1,1,1,2,2,3}
result := computeResult(input, 2)
fmt.Println("result:", result)
}
func computeResult(input []int, k int) []int {
filter := map[int]int {}
for i := 0; i < len(input); i++ {
if _, exists := filter[input[i]]; exists {
filter[input[i]] += 1
} else {
filter[input[i]] = 1
}
}
h := &IHeap{}
heap.Init(h)
for key, value := range filter {
heap.Push(h, [2]int{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
result := make([]int, k)
// 小顶堆是最小的在最上面，最先被Pop出来
for i := 0; i < k; i++ {
result[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return result
}
type IHeap struct {
items [][2]int
}
func (h *IHeap) Push(x interface{}) {
h.items = append(h.items, x.([2]int))
}
func (h *IHeap) Len() int {
return len(h.items)
}
// 构建小顶堆
func (h *IHeap) Less(i, j int) bool {
return h.items[i][1] < h.items[j][1]
}
func (h *IHeap) Swap(i, j int) {
h.items[i], h.items[j] = h.items[j], h.items[i]
}
func (h *IHeap) Pop() interface{} {
n := h.Len()
item := h.items[n - 1]
h.items = h.items[0: n - 1]
return item
}寻找峰值
[题目]
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
[输入1]
nums = [1,2,3,1][返回1]
2[输入2]
nums = [1,2,1,3,5,6,4][返回2]
1 或 5[解法]
因为题目中只需要返回一个，那么我们可以使用类似二叉树遍历，需要注意下面都是mid + 1，这是因为整数除以2，会向下取整，e.g. (2 + 3) / 2 = 2。算法的复杂度为O(logn)
[代码实现]
package main
import "fmt"
func main() {
input := []int {1,2,1,3,5,6,4}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) int {
left := 0
right := len(input) - 1
for left < right {
mid := (left + right) / 2
if input[mid] > input[mid + 1] {
right = mid
} else {
left = mid + 1
}
}
return left
}在排序数组中查找元素的第一个和最后一个位置
[题目]
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
[输入1]
nums = [5,7,7,8,8,10], target = 8[返回1]
[3,4][输入2]
nums = [5,7,7,8,8,10], target = 6[返回2]
[-1,-1][解法]
排序好的数组，使用二分查找，向前计算开头元素的下标。注意计算尾部下标的时候，可以计算target + 1元素的首个下标，这个下标减去1，就是target尾部下标
[代码实现]
package main
import "fmt"
func main() {
input := []int {5,7,7,8,8,10}
target := 8
result := computeResult(target, input)
fmt.Println("result:", result)
}
func computeResult(target int, input []int) []int {
before := beforeIndex(target, input)
after := beforeIndex(target + 1, input)
if after == -1 {
after = before
}
return []int { before, after }
}
func beforeIndex(target int, input []int) int {
left := 0
right := len(input) - 1
for left < right {
mid := (left + right) / 2
if target == input[mid] {
return mid
} else if target > input[mid] {
left = mid + 1
} else {
right = mid + 1
}
}
return -1
}