day13|239.滑动窗口最大值347.前K个高频元素-创新互联

文章目录

• 239. 滑动窗口大值
• • 1、代码1（超出时间限制）
  • 2、代码2
  • 3、分析
• 347.前 K 个高频元素
• • 1、代码1
  • 2、分析
  • 3、代码2
  • 4、代码3
  • 5、分析

创新互联主要从事成都网站建设、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务通山,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792

---

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;
    }
}

2、代码2

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;
    }
}

3、分析

（1）代码1使用了同向双指针的滑动窗口进行循环求解，可惜数据量太大的时候超出时间限制。
（2）代码2通过新写一个类封装数据结构的方式进行求解。代码2通过deque队列封装了一个单调递减队列。当然，在不同的题目中封装的方法各不相同，具体形式依题目而定。
（3）Myqueue的poll()函数是当队首元素等于滑动窗口左侧边缘时将其poll出队列。
add()函数是将数组的新元素加入队列并进行单调递减排列。当新元素大的时候将队列的其他元素poll出去，否则按照单调递减的顺序进行排列。peek()函数是返回队列的大元素。
（4）本题的难点是自己实现一个单调队列，很难想到这个思路。

347.前 K 个高频元素 1、代码1

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;
    }
}

2、分析

（1）既然是将数组转化为哈希map，那么数组排序就显得多余。这里还是对map的api等等不熟悉，由值取不到键，也没有考虑到其他数据结构。

3、代码2

class 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;
    }
}

4、代码3

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;
    }
}

5、分析

（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://kswsj.com/article/pochi.html