刷题打卡，第五天
题目一、（简单题）1464. 数组中两元素的最大乘积
题目二、(中等题)347. 前 K 个高频元素
题目三、(困难题)2163. 删除元素后和的最小差值
题目一、（简单题）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; } }
提交结果：
贵在坚持：🎇关注作者，共同进步…
