题目一、（简单题）1464. 数组中两元素的最大乘积

原题链接：1464. 数组中两元素的最大乘积

题目描述：

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[ i ] - 1)*(nums[ j ] - 1) 取得最大值。

请你计算并返回该式的最大值。

解题思路：
这道题十分简单，当作热身吧。
要选择下标 i 与 j 让 (nums[ i ] - 1)*(nums[ j ] - 1) 取得最大值。
我们不需要纠结选择哪两个下标才能取到最大值，直接为数组排序，选择最大的两个元素分别减1再相乘即可。
我使用的是最大堆为数组元素排序。

解题代码：

class Solution {
    public int maxProduct(int[] nums) {
        //创建优先队列，因为默认为最小堆
        //所以需要重写比较器，设置为最大堆
        PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return b - a;
            }
        });
        
        //数组元素放入最大优先队列
        for(int num : nums){
            que.offer(num);
        }

        //取出两个堆顶节点，就是题目所求可获取最大值的nums[i]与nums[j]，分别减一
        int a = (int)que.poll()-1;
        int b = (int)que.poll()-1;

        //返回(nums[i]-1)*(nums[j]-1)
        return a*b;

    }
}

提交结果：

题目二、(中等题)347. 前 K 个高频元素

原题链接：347. 前 K 个高频元素

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

/

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]
/
示例 2:

输入: nums = [1], k = 1

输出: [1]

解题思路：
用HashMap的键值对{key-value对}存放数组元素与元素出现的次数。
key： 数组中出现过的元素
value： 元素出现的频率
遍历map集合，将键值对以长度为2的一维数组形式放入最大堆排序：
一维数组 int [ ] {key，value}
排序按照数组中的value大小排序。
最后输出排序好的，前k个高频元素。
具体实现可以看代码，注释详细：

代码：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //创建优先队列，优先队列存放的是长度为2的一维数组：int[]{key,value}
        //1.int [0] = key代表数组nums中出现过的元素
        //2.int [1] = value代表对应元素出现的频率
        //重写比较器，将优先队列设置为最大堆，按照value值（频率）的优先顺序排序。
        PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return b[1]-a[1];
            }
        });
        //创建双列集合map，存放键值对key-value
        Map<Integer,Integer> map = new HashMap<>();
        //增强for循环遍历数组
        for(int num : nums){
            //如果已经存在以数组某个元素为key的键值对
            if(map.containsKey(num)){
                //对应键值对中的value值加一
                map.replace(num,map.get(num).intValue()+1);
            }else{//否则
                  //创建以元素为主键key的键值对，value值为1
                map.put(num,1);
            }
        }
        
        //使用迭代器遍历map集合中的键值对
        Iterator<Map.Entry<Integer,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Integer,Integer> entry = iterator.next();
            //将键值对以长度为2的一维数组形式放入最大堆排序
            que.offer(new int[]{entry.getKey(),entry.getValue()});
        }

        //创建长度为k的数组
        int[] out = new int[k];
        //遍历地将出现频率前k高的元素放入数组
        for(int i = 0;i < k; ++i){
            out[i] = (int)que.poll()[0];
        }

        //输出出现频率前 k 高的元素
        return out;

    }
}

提交结果：

题目三、(困难题)2163. 删除元素后和的最小差值

原题链接：2163. 删除元素后和的最小差值

题目描述：

解题思路：
舒勇两个优先队列，一个最小堆，一个最大堆。
创建两个数组，分别存放最小和与最大和的所有情况。
最后将所有情况中最小的差值输出。

代码：

class Solution {
    public long minimumDifference(int[] nums) {
        int n = nums.length / 3;
        // min[i] 表示 nums[0] ~ nums[i] 个元素中选择 n 个元素和最小
        long[] min = new long[3 * n];

        // max[i] 表示 nums[i] ~ nums[3*n-1] 个元素中选择 n 个元素和最大
        long[] max = new long[3 * n];

        // 升序队列、 降序队列
        PriorityQueue<Integer> asc = new PriorityQueue<>();
        PriorityQueue<Integer> desc = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return b-a;
            }
        });
        
        long sum_first = 0, sum_second = 0;
        for (int i = 0; i < 3 * n; i++) {
            int l = i, r = 3 * n - 1 - i;
            int left = nums[l], right = nums[r];
            sum_first += left;
            desc.add(left);

            sum_second += right;
            asc.add(right);

            if (i >= n) {
                sum_first -= desc.poll();
                sum_second -= asc.poll();
            }
            min[l] = sum_first;
            max[r] = sum_second;
        }

        // 遍历所有情况找到最小差值
        long minAns = Long.MAX_VALUE;
        for (int i = n - 1; i < 2 * n; i++) {
            minAns = Math.min(minAns, min[i] - max[i + 1]);
        }

        return minAns;
    }
}

提交结果：