湖南的商城网站建设,网站建设与管理专业就业,网站建设属于什么岗位,建设行业管理信息系统官网目录 239. 滑动窗口最大值347.前 K 个高频元素方法一方法二 239. 滑动窗口最大值
链接
窗口 — 维持一个单调递增队列
为什么要使用队列#xff1f;
在窗口移动的时候#xff0c;方便把不属于窗口的最大值剔除。#xff08;当窗口移动之后#xff09;
class Solution:… 目录 239. 滑动窗口最大值347.前 K 个高频元素方法一方法二 239. 滑动窗口最大值
链接
窗口 — 维持一个单调递增队列
为什么要使用队列
在窗口移动的时候方便把不属于窗口的最大值剔除。当窗口移动之后
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:q deque() # store indexres []l r 0while r len(nums):# push# make sure that its a mono increasing queuewhile q and nums[q[-1]] nums[r]:q.pop()q.append(r)# pop element # since its not in the window anymoreif l q[0]:q.popleft()# append the max num in the window to res# only when a window is formed can we move the l pointerif (r 1) k:res.append(nums[q[0]])l 1r 1return res347.前 K 个高频元素
链接
方法一
Counter得到频率表反转频率表再进行heapify。 heappop前k个元素即为前K个高频元素。
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:_map Counter(nums)_map [(-v, i) for i, v in _map.items()]heapify(_map)res []for i in range(k):want heappop(_map)res.append(want[1])return res方法二
Bucket Sort
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:_map Counter(nums)freq [[] for i in range(len(nums) 1)]for key, val in _map.items():freq[val].append(key)res []for i in range(len(freq) - 1, 0, -1):while freq[i] and k 0:res.append(freq[i].pop())k - 1if k 0:breakreturn res
