day13|239.滑动窗口最大值347.前K个高频元素-创新互联
- 239. 滑动窗口大值
- 1、代码1（超出时间限制）
- 2、代码2
- 3、分析
- 347.前 K 个高频元素
- 1、代码1
- 2、分析
- 3、代码2
- 4、代码3
- 5、分析
239. 滑动窗口大值 1、代码1（超出时间限制）
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int left = 0;
int right = k-1;
int max = Integer.MIN_VALUE;
int index = 0;
int[] array = new int[nums.length - k + 1];
while(right< nums.length){for(int i=left; i<=right; i++){if(max< nums[i]){max = nums[i];
}
}
array[index++] = max;
max = Integer.MIN_VALUE;
right++;
left++;
}
return array;
}
}
class MyQueue{//用deque封装一个单调队列
Dequedeque = new LinkedList<>();//
void poll(int val){if(!deque.isEmpty() && val == deque.peek()){deque.poll();
}
}
void add(int val){while(!deque.isEmpty() && val >deque.getLast()){deque.removeLast();
//使队列在有效范围内单调
}
deque.add(val);
}
int peek(){return deque.peek();
}
}
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] result = new int[nums.length - k + 1];
MyQueue que = new MyQueue();//
int index = 0;
for(int i=0; ique.add(nums[i]);
}
result[index++] = que.peek();
for(int i=k; ique.poll(nums[i - k]);//
que.add(nums[i]);
result[index++] = que.peek();
}
return result;
}
} （1）代码1使用了同向双指针的滑动窗口进行循环求解，可惜数据量太大的时候超出时间限制。
（2）代码2通过新写一个类封装数据结构的方式进行求解。代码2通过deque队列封装了一个单调递减队列。当然，在不同的题目中封装的方法各不相同，具体形式依题目而定。
（3）Myqueue的poll()函数是当队首元素等于滑动窗口左侧边缘时将其poll出队列。
add()函数是将数组的新元素加入队列并进行单调递减排列。当新元素大的时候将队列的其他元素poll出去，否则按照单调递减的顺序进行排列。peek()函数是返回队列的大元素。
（4）本题的难点是自己实现一个单调队列，很难想到这个思路。
class Solution {public int[] topKFrequent(int[] nums, int k) {Arrays.sort(nums);
Mapmap = new HashMap<>();
if(nums.length == 1){return nums;
}
int count = 0;
for(int i=0; iif(i == 0 && nums[i] == nums[i+1]){map.put(nums[i],++count);
}
if(map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i]) + 1);
}else{map.put(nums[i],1);
}
}
int[] result = new int[k];
int index;
while(k >1){int max = Integer.MIN_VALUE;
for(int i=0; iif(map.get(nums[i]) >max){max = map.get(nums[i]);
map.put(nums[i],0);
result[k-1] = nums[i];
System.out.println(result[k-1]);
}
}
k--;
}
return result;
}
}
（1）既然是将数组转化为哈希map，那么数组排序就显得多余。这里还是对map的api等等不熟悉，由值取不到键，也没有考虑到其他数据结构。
3、代码2class Solution {public int[] topKFrequent(int[] nums, int k) {//转化为哈希形式
Mapmap = new HashMap<>();
for(int num : nums){map.put(num,map.getOrDefault(num,0) + 1);
}
//创建小顶堆
PriorityQueuepq = new PriorityQueue<>((pair1,pair2)->pair1[1] -pair2[1]);
for(Map.Entryentry : map.entrySet()){if(pq.size()< k){//小与大的区别
pq.add(new int[]{entry.getKey(),entry.getValue()});
}else{if(entry.getValue() >pq.peek()[1]){pq.poll();
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
//小顶堆的结果赋给数组
int[] result = new int[k];
for(int i=0; iresult[i] = pq.poll()[0];
}
return result;
}
}
class Solution {public int[] topKFrequent(int[] nums, int k) {//转化为map形式
Mapmap = new HashMap<>();
for(int num : nums){map.put(num,map.getOrDefault(num,0) + 1);
}
//大顶堆
PriorityQueuepq = new PriorityQueue<>((pair1,pair2)->(pair2[1]-pair1[1]));
for(Map.Entryentry : map.entrySet()){pq.add(new int[]{entry.getKey(),entry.getValue()});
}
//大顶堆赋给数组
int[] result = new int[k];
for(int i=0; iresult[i] = pq.poll()[0];
}
return result;
}
}
（1）代码：
map.put(num,map.getOrDefault(num,0) + 1);map.getOrDefault()的意思是如果map中key已经存在，则返回key对应的value；若不存在，则返回0。程序将数组进行遍历并且将元素的值和频率存到map。
（2）程序使用优先级队列（**底层用堆实现，堆就是一颗完全二叉树，同时保证父子节点的顺序关系。**将队列按单调顺序进行排列）将map单调排列。
PriorityQueuepq = new PriorityQueue<>((pair1,pair2)->(pair2[1]-pair1[1])); 1）当函数体的第一个参数排在前面（pair1[1]-pair2[1]），返回负数，表示优先级队列按小到大的顺序排列 - >小顶堆。
2）当函数体的第二个参数排在前面（pair2[1]-pair1[1]），返回正数，表示优先级队列按大到小的顺序排列 - >大顶堆。
（3）小顶堆由于是按从小到大排序的，所以在入满 k 个map之后要根据map的value进行筛选，否则最后在需要返回元素时候需要的元素都排在队尾。
而大顶堆则是消耗一些时间复杂度将优先级队列从大到小进行排序，最后在返回元素时直接返回前三个元素，从程序书写层面来说比较简单。
（4）用Map.Entry（）初始化的entry遍历map.entrySet()可以同时取得map的键和值。
（5）初始化数组接收队列poll出来的value。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享题目：day13|239.滑动窗口最大值347.前K个高频元素-创新互联
网页链接：http://pwwzsj.com/article/pochi.html
