当前位置：首页 > news >正文

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

news 2025/8/2 10:24:45

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]
}

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:]}
}