难度: Medium
给定两个长度相等的数组 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]
提示：
1 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 109运行时间: 108 ms
内存: 33.1 MB
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
nums1.sort()
i2 = sorted(range(n), key=lambda i: nums2[i])
ans = [-1] * n
L, R = 0, n - 1
for val in nums1:
if val > nums2[i2[L]]:
ans[i2[L]] = val
L += 1
else:
ans[i2[R]] = val
R -= 1
return ans
这个题解采用了贪心算法的思想。首先，对nums1进行排序，以便尽可能将较小的值与nums2中较小的值匹配。同时，对nums2的索引进行排序，基于nums2的值进行排序，以便我们可以从nums2的最小值开始尝试匹配。接着，我们遍历排序后的nums1，尝试为每个nums2中的值找到一个大于它的最小nums1中的值。如果nums1中的当前值大于nums2中当前考虑的最小值，我们就把这个值分配给它，以此来最大化优势。如果不大于，则把这个值分配给当前nums2中的最大值的位置，尽可能减小'损失'。通过这种方式，我们可以保证nums1的优势最大化。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
nums1.sort() # 对nums1进行排序
i2 = sorted(range(n), key=lambda i: nums2[i]) # 根据nums2的值对其索引进行排序
ans = [-1] * n # 初始化结果数组
L, R = 0, n - 1 # 设置双指针，L用于较小的匹配，R用于较大的匹配
for val in nums1: # 遍历排序后的nums1
if val > nums2[i2[L]]: # 如果当前nums1的值可以给nums2的当前最小值优势
ans[i2[L]] = val # 分配并移动L指针
L += 1
else: # 如果不能优势，给当前nums2的最大值
ans[i2[R]] = val # 分配并移动R指针
R -= 1
return ans # 返回最终结果数组
在算法中，nums1 排序的目的是为了能够从小到大尝试为 nums2 的元素寻找优势值。如果直接对 nums2 排序，虽然可以按照从小到大处理 nums2 的元素，但这会改变 nums2 元素的原始位置，从而无法将优势值正确地放回原数组的对应位置。通过对 nums2 的索引进行排序，我们既保留了能够按值处理的顺序，又能通过索引将计算的结果放回到原始的数组结构中，这对解题是非常关键的。
这种策略的核心思想是尽量利用 nums1 中的较小值去匹配 nums2 中的较大值，从而将这些较小值的影响最小化。如果 nums1 中的值无法给 nums2 中的当前最小值带来优势，那么这个 nums1 的值相对较小，将其匹配到 nums2 中的最大值上，可以避免浪费一个较大的 nums1 值在一个大的 nums2 值上，这样可以为后续的匹配留下更有优势的 nums1 值，从而在整体上减小了“损失”。
双指针 L 和 R 在算法中分别指向 nums2 索引排序后的最小位置和最大位置。L 用于尝试寻找可以给 nums2 中当前最小值带来优势的 nums1 值，如果当前遍历到的 nums1 值大于 nums2[i2[L]]（nums2 索引排序后的当前最小值），则将这个 nums1 值分配给它，并将 L 指针向右移动，即向更大的值移动。如果当前 nums1 值不能优势当前考虑的 nums2 的最小值，那么用 R 指针指向的位置，即 nums2 中的最大值位置分配这个 nums1 值，然后将 R 指针向左移动，即向更小的值移动。这样的策略不仅使得能够优势的情况下尽可能利用，而且在不能优势的情况下尽可能减小损失。