【LeetCode】优势洗牌 Java 题解
题目描述
给定两个大小相等的数组 nums1 和 nums2,nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列,使其相对于 nums2 的优势最大化。
复制代码
思路分析
今天的算法题目是数组题目。题目描述是优势洗牌,要求是 nums1 任意排列的最大话。通过例子分析,就是对于下标 i, 先找 nums1 中,大于 num2[i] 的最小值,如果没有的话,就将 nums[1] 中的最小值放到这个位置。这样一分析,是不是和我们学过的课文《田忌赛马》一样。"今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。"就是这次博弈的重点。
理解了题目含义之后,nums2 的顺序是固定的,我们需要对 nums1 的元素进行排序,这里可以使用 TreeSet 这种数据结构,TreeSet 底层是实现是红黑树。其中,ceiling() 可以用于查找大于或等于参数列表中给定元素的元素,如果找不到的时候,会返回 null。当返回 null 的时候,我们可以直接找最小的元素放入。由于 nums1 中的元素可能有重复,我们使用 HashMap 记录元素出现的个数,当元素个数为 0 时,我们直接在 treeSet 中移除这个元素。
具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n log n),空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/f10609c3b090fb81ee3a43b77】。文章转载请联系作者。
评论