【LeetCode】优势洗牌 Java 题解

作者：Albert

2022 年 10 月 09 日
北京
本文字数：1108 字
阅读完需：约 4 分钟

题目描述

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]输出：[2,11,7,15]示例 2：
输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]输出：[24,32,8,12] 
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/advantage-shuffle著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目。题目描述是优势洗牌，要求是 nums1 任意排列的最大话。通过例子分析，就是对于下标 i, 先找 nums1 中，大于 num2[i] 的最小值，如果没有的话，就将 nums[1] 中的最小值放到这个位置。这样一分析，是不是和我们学过的课文《田忌赛马》一样。"今以君之下驷与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。"就是这次博弈的重点。
理解了题目含义之后，nums2 的顺序是固定的，我们需要对 nums1 的元素进行排序，这里可以使用 TreeSet 这种数据结构，TreeSet 底层是实现是红黑树。其中，ceiling() 可以用于查找大于或等于参数列表中给定元素的元素，如果找不到的时候，会返回 null。当返回 null 的时候，我们可以直接找最小的元素放入。由于 nums1 中的元素可能有重复，我们使用 HashMap 记录元素出现的个数，当元素个数为 0 时，我们直接在 treeSet 中移除这个元素。
具体实现代码如下，供参考。

通过代码

class Solution {    public int[] advantageCount(int[] nums1, int[] nums2) {        int n = nums1.length;        int[] ans = new int[n];        TreeSet<Integer> treeSet = new TreeSet<>();        Map<Integer, Integer> map = new HashMap<>();        int cnt = 0;        for (int num : nums1) {            cnt = map.getOrDefault(num, 0) + 1;            map.put(num, cnt);            if (cnt == 1) {                treeSet.add(num);            }        }
        for (int i = 0; i < n; i++) {            Integer temp = treeSet.ceiling(nums2[i] + 1);            if (temp == null) {                temp = treeSet.ceiling(-1);            }            ans[i] = temp;            cnt = map.getOrDefault(temp, 0) - 1;            map.put(temp, cnt);            if (cnt == 0) {                treeSet.remove(temp);            }        }
        return ans;    }}