每日刷题_

这篇具有很好参考价值的文章主要介绍了每日刷题_。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前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;
        HashMap<Integer, 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);
        }

      
        List<Map.Entry<Integer, 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];
        HashMap<Integer, Integer> map = new HashMap<>();
        //这里是大顶堆
         PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0) +1);   //default
           
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        for(int i =0;i<k;i++){
            ak[i] = pq.poll()[0];
        }

        return ak;
    }
}

3、小根堆

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ak = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        //这里是大顶堆
        // PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);

        //小根堆
         PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0) +1);   //default
           
        }
        for(Map.Entry<Integer,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 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

因为刚学到了优先队列,想的是直接用这个优先队列暴力破解,但是没有想到的是数据量确实太大了,直接失败了。

 

后面真正解法是:

自己定义一个类,然后类中定义一个变量,双向队列,然后模拟优先队列的方法来实现文章来源地址https://www.toymoban.com/news/detail-737226.html

class myQueue{
    //这里是双端队列,双向队列是指该队列两端的元素既能入队(offer)也能出队(poll)
    Deque<Integer> 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;
    }
}

到了这里,关于每日刷题_的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包