建设银行官网学生交费网站,网络营销专业的就业方向,自己做网站需要收费吗,阿里云网站建设教学视频教程前k个高频元素
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 一共有三种不同的题解#xff1a; 1、把数据存到哈希表中#xff0c;然后通过哈希表来排序#xff0c;时间复杂度…前k个高频元素
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 一共有三种不同的题解 1、把数据存到哈希表中然后通过哈希表来排序时间复杂度n*logn 2、大根堆 k*logn 3、小根堆 k*logn 这里的大/小根堆数据结构Java中都是有的就是 优先队列PriorityQueue 第一种解法
public class Solution {public int[] topKFrequent(int[] nums, int k) {int[] ak new int[k];int cnt 0;HashMapInteger, Integer map new HashMap();int len nums.length;for (int i 0; i len; i) {map.put(nums[i], map.getOrDefault(nums[i], 0) 1);}ListMap.EntryInteger, Integer list new ArrayList(map.entrySet());list.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));for (int i 0; i k; i) {ak[cnt] list.get(i).getKey();}return ak;}
}
大根堆
public class Solution {public int[] topKFrequent(int[] nums, int k) {int[] ak new int[k];HashMapInteger, Integer map new HashMap();//这里是大顶堆PriorityQueueint[] pq new PriorityQueue((pair1, pair2)-pair2[1]-pair1[1]);for(int num : nums){map.put(num, map.getOrDefault(num,0) 1); //default}for(Map.EntryInteger,Integer entry : map.entrySet()){pq.add(new int[]{entry.getKey(),entry.getValue()});}for(int i 0;ik;i){ak[i] pq.poll()[0];}return ak;}
} 3、小根堆
public class Solution {public int[] topKFrequent(int[] nums, int k) {int[] ak new int[k];HashMapInteger, Integer map new HashMap();//这里是大顶堆// PriorityQueueint[] pq new PriorityQueue((pair1, pair2)-pair2[1]-pair1[1]);//小根堆PriorityQueueint[] pq new PriorityQueue((pair1, pair2)-pair1[1]-pair2[1]);for(int num : nums){map.put(num, map.getOrDefault(num,0) 1); //default}for(Map.EntryInteger,Integer entry : map.entrySet()){// pq.add(new int[]{entry.getKey(),entry.getValue()});if(pq.size()k){//小顶堆元素个数小于k个时直接加pq.add(new int[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue()pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new int[]{entry.getKey(),entry.getValue()});}}}for(int i k-1;i 0 ;i--){ak[i] pq.poll()[0];}return ak;}
} 239. 滑动窗口最大值
力扣题目链接(opens new window)
给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。 因为刚学到了优先队列想的是直接用这个优先队列暴力破解但是没有想到的是数据量确实太大了直接失败了。 后面真正解法是 自己定义一个类然后类中定义一个变量双向队列然后模拟优先队列的方法来实现 class myQueue{//这里是双端队列双向队列是指该队列两端的元素既能入队offer也能出队(poll)DequeInteger deque new LinkedList();void poll(int val){if(!deque.isEmpty() deque.peek() val)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) {if (nums.length 1) {return nums;}int len nums.length - k 1;//存放结果元素的数组int[] res new int[len];int cnt 0;myQueue myQueue new myQueue();//先将前k的元素放入队列for (int i 0; i k; i) {myQueue.add(nums[i]);}res[cnt] myQueue.peek();for (int i k; i nums.length; i) {//滑动窗口移除最前面的元素移除是判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[cnt] myQueue.peek();}return res;}
}
