写点什么

【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; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n log n),空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 3
用户头像

Albert

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】优势洗牌Java题解_LeetCode_Albert_InfoQ写作社区