滑动窗口大值
这是做过的第一个困难题目, 虽然看起来不是很难, 但是有一些细节要注意
总体思路: 队列存的是下标, 并且数组中的数要从大到小排序
有三个重要点:
while循环判断, 如果nums[deque.peekLast]小于val, 那么就要removeLast, 同时把val加上
如果deque.peekFirst在nums[i-k]窗口之外了, 就要removeFirst
如果i ≥ k- 1也就是窗口被填满了, 那么就开始存max
细节:
1.首先需要一个队列, 一个数组, 一个默认值inde, 队列用来保存下标, 数组保存大值, index用来给数组计数
2.关键就是让这个窗口移动, 向右移要判断之后pollLast, 然后offerLast
3. 首先用一个while, 然后窗口的pollFirst和添加数组用if就行了
4.记住这里最后的数组长度就是nums.length - k + 1, 也就是滑动窗口的个数
5. i - k + 1代表着这个窗口左侧, 需要判断队列的first在不在窗口内这里要包括等于号啊
6.最后的判断别忘了边界处理大于等于窗口大小
总结,滑动窗口三步走
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//存下标可以更方便的来确定元素是否需要移出滑动窗口
//判断下标是否合法来确定是否要移出
Dequeq = new LinkedList<>();
//res就是最后的长度, 也就是总共窗口的长度
int[] res = new int[nums.length - k + 1] ;
int index = 0;
for(int i = 0; i< nums.length; i++){
//保证队列的单调递减，使队列的出口始终为大值(窗口右移)
//注意队列存的是数组下标，所以判断逻辑是nums[i] >nums[q.peekLast()]
//容易误写成nums[i] >q.peekLast()
while(!q.isEmpty() && nums[i] >nums[q.peekLast()]){
q.pollLast();
}
q.offerLast(i);
//判断队列出口的值是否合法，如果值的下标不在窗口内则要将其移出
if(q.peek()<= i - k){
q.pollFirst();
}
//窗口至少填满一次后才开始放大值
//依然要注意队列存的是下标，所以赋值是赋nums[q.peekFirst()]
if(i >= k - 1){
res[index++] = nums[q.peek()];
}
}
return res;
}
} 前k个高频元素
这道题思路其实不难, 但是设计很多基础的数据结构知识, 我都不熟悉, 导致做得很折磨
思路(大顶堆): 复杂度nLogn
细节:
1. 创建优先队列涉及到lambda表达式和comparator
2.最后遍历数据没有理解结构pq.poll()[0]是什么意思
这里先上代码, 需要把排序和集合巩固之和才能完全理解, lambda和comparator如下
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//先把数组的key和value放到哈希表里面
HashMaphash = new HashMap<>();
for(int num : nums){
if(hash.containsKey(num)){
hash.put(num, hash.get(num) + 1);
} else{
hash.put(num, 1);
}
}
//然后把哈希表的数字放到优先队列里, 这里涉及到lambda表达式
PriorityQueuepq = new PriorityQueue<>((pair1, pair2) ->pair2[1] - pair1[1]);
for(Map.Entryentry : hash.entrySet()){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
//已经自动排好序了, 直接创建数组导出来就行了
int[] ans = new int[k];
for(int i = 0; i< k; i++){
ans[i] = pq.poll()[0];
}
return ans;
}
} 小顶堆: 复杂度nLogk
由于时间关系暂时不搞了, 周末再来看
public int[] topKFrequent2(int[] nums, int k) {
Mapmap = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
PriorityQueuepq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
for(Map.Entryentry:map.entrySet()){//小顶堆只需要维持k个元素有序
if(pq.size()pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] ans = new int[k];
for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
ans[i] = pq.poll()[0];
}
return ans;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧