题目形容
这是 LeetCode 上的 870. 劣势洗牌 ，难度为 中等。
Tag : 「红黑树」、「哈希表」、「排序」、「双指针」、「贪婪」
给定两个大小相等的数组 nums1 和 nums2，nums1 绝对于 nums 的劣势能够用满足 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]提醒：
- $1 <= nums1.length <= 10^5$
- nums2.length = nums1.length
- $0 <= nums1[i]$, $nums2[i] <= 10^9$
数据结构
显然，对于任意一个 $t = nums2[i]$ 而言，咱们该当在候选汇合中抉择比其大的最小数，若不存在这样的数字，则抉择候选汇合中的最小值。
同时，因为 $nums1$ 雷同数会存在多个，咱们还要对某个具体数字的可用次数进行记录。
也就是咱们总共波及两类操作：
- 实时保护一个候选汇合，该汇合反对高效查问比某个数大的数值操作；
- 对候选汇合中每个数值的可应用次数进行记录，当应用到了候选汇合中的某个数后，要对其进行计数减一操作，若计数为 $0$，则将该数值从候选汇合中移除。
计数操作容易想到哈希表，而实时保护候选汇合并高效查问能够应用基于红黑树的 TreeSet 数据结构。
Java 代码：
class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; TreeSet<Integer> tset = new TreeSet<>(); Map<Integer, Integer> map = new HashMap<>(); for (int x : nums1) { map.put(x, map.getOrDefault(x, 0) + 1); if (map.get(x) == 1) tset.add(x); } int[] ans = new int[n]; for (int i = 0; i < n; i++) { Integer cur = tset.ceiling(nums2[i] + 1); if (cur == null) cur = tset.ceiling(-1); ans[i] = cur; map.put(cur, map.get(cur) - 1); if (map.get(cur) == 0) tset.remove(cur); } return ans; }}Python 代码：
from sortedcontainers import SortedListclass Solution: def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]: n = len(nums1) cnts, tset = defaultdict(int), SortedList() for i in range(n): cnts[nums1[i]] += 1 if cnts[nums1[i]] == 1: tset.add(nums1[i]) ans = [0] * n for i in range(n): t = nums2[i] if (idx := tset.bisect_left(t + 1)) == len(tset): idx = tset.bisect_left(-1) ans[i] = tset[idx] cnts[ans[i]] -= 1 if cnts[ans[i]] == 0: tset.remove(ans[i]) return ans- 工夫复杂度：$O(n\log{n})$
- 空间复杂度：$O(n)$
排序 + 双指针
在解法一中，咱们是从每个 $nums2[i]$ 登程思考，应用哪个 $nums1[i]$ 去匹配最为适合。
实际上，咱们也能从 $nums1[i]$ 登程，思考将其与哪个 $nums2[i]$ 进行匹配。
为了让每个决策回合具备独立性，咱们须要对两数组进行排序，同时为了在结构答案时，可能对应回 nums2 的原下标，排序前咱们须要应用「哈希表」记录每个 $nums2[i]$ 的下标为何值。
应用变量 l1 代表以后决策将 $nums1[l1]$ 调配到哪个 nums2 的地位，应用 l2 和 r2 代表以后 nums2 中还有 $[l2, r2]$ 地位还待填充。
能够证实咱们在从前往后给每个 $nums1[l1]$ 调配具体位置时，调配的地位只会在 l2 和 r2 两者之间产生。
Java 代码：
class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < n; i++) { List<Integer> list = map.getOrDefault(nums2[i], new ArrayList<>()); list.add(i); map.put(nums2[i], list); } Arrays.sort(nums1); Arrays.sort(nums2); int[] ans = new int[n]; for (int l1 = 0, l2 = 0, r2 = n - 1; l1 < n; l1++) { int t = nums1[l1] > nums2[l2] ? l2 : r2; List<Integer> list = map.get(nums2[t]); int idx = list.remove(list.size() - 1); ans[idx] = nums1[l1]; if (t == l2) l2++; else r2--; } return ans; }}Python 代码：
class Solution: def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]: n = len(nums1) mapping = defaultdict(list) for i in range(n): mapping[nums2[i]].append(i) nums1.sort() nums2.sort() ans = [0] * n l2, r2 = 0, n - 1 for l1 in range(n): t = l2 if nums1[l1] > nums2[l2] else r2 ans[mapping[nums2[t]].pop()] = nums1[l1] if t == l2: l2 += 1 else: r2 -= 1 return ans- 工夫复杂度：$O(n\log{n})$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.870 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布