【代码随想录】算法训练计划13

1、347. 前 K 个高频元素

题目：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路：

• sort.Slice学习一下，其实还有sort.String等

func topKFrequent(nums []int, k int) []int {
    // 代码一刷，快排，或者小/大顶堆
    map1 := make(map[int]int, 0)
    for _,v := range nums {
        map1[v]++
    }
    ans := []int{}
    for k,_ := range map1 {
        ans = append(ans, k)
    }
    sort.Slice(ans, func(a,b int)bool{
        return map1[ans[a]]>map1[ans[b]]
    })
    return ans[:k]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、239. 滑动窗口最大值

题目：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

思路：

• 1、为什么pop时候要：val == m.Front()
• 2、queue.Push(nums[i]) // 5432咋办

func maxSlidingWindow(nums []int, k int) []int {
    queue := NewMyQueue()
    length := len(nums)
    res := make([]int, 0)
    for i:=0; i<k; i++ {
        queue.Push(nums[i]) // 5432咋办
    }
    res = append(res, queue.Front())
    for i := k; i<length; i++ {
        queue.Pop(nums[i-k])
        queue.Push(nums[i])
        res = append(res, queue.Front())
    }
    return res
}
// 单调队列
type MyQueue struct {queue []int}
func NewMyQueue() *MyQueue {
    return &MyQueue{
        queue: make([]int, 0),
    }
}
func (m *MyQueue) Front() int {return m.queue[0]}
func (m *MyQueue) Back() int {return m.queue[len(m.queue)-1]}
func (m *MyQueue) Empty() bool {return len(m.queue)==0}
func (m *MyQueue) Push(val int) {
    for !m.Empty() && val>m.Back() {
        m.queue = m.queue[:len(m.queue)-1]
    }
    m.queue = append(m.queue, val)
}
func (m *MyQueue) Pop(val int) {
    if !m.Empty() && val == m.Front() {
        m.queue = m.queue[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