来源：力扣（LeetCode）

描述：

  给定两个大小相等的数组 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⁵

• nums2.length == nums1.length

• 0 <= nums1[i], nums2[i] <= 10⁹

方法：贪心算法

思路与算法

我们首先分别将数组 nums₁ 和 nums₂ 进行排序，随后只需要不断考虑这两个数组的首个元素：

• 如果 nums₁ 的首个元素大于 nums₂ 的首个元素，那么就将它们在答案中对应起来，同时从数组中移除这两个元素，并增加一点「优势」；

• 如果 nums₁ 的首个元素小于等于nums₂ 的首个元素，那么移除 nums₁ 的首个元素。

当 nums₁ 中没有元素时，遍历结束。

这样做的正确性在于：

• 对于第一种情况，由于 nums₁ 是有序的，那么 nums₁ 的任意元素大于 nums₂ 的首个元素：

  • 如果我们不与 nums₂ 的首个元素配对，由于 nums₂ 是有序的，之后的元素会更大，这样并不划算；
  • 如果我们与 nums₂ 的首个元素配对，我们使用 nums₁ 的首个元素，可以使得剩余的元素尽可能大，之后可以获得更多「优势」。

• 对于第二种情况，由于 nums₂ 是有序的，那么 nums₁ 的首个元素小于等于 nums₂ 中的任意元素，因此nums₁ 的首个元素无法增加任何「优势」，可以直接移除。

在本题中，由于 nums₁ 中的每一个元素都要与 nums₂ 中的元素配对，而我们是按照顺序考虑 nums₂ 中的元素的。因此在遍历结束后，nums₂ 中剩余的元素实际上是原先 nums₂ 的一个后缀。因此当 nums₁ 的首个元素无法配对时，我们给它配对一个 nums₂ 的尾元素即可，并将该尾元素移除。

在实际的代码编写中，我们无需真正地「移除」元素。对于 nums₁，我们使用一个循环依次遍历其中的每个元素；对于 nums₂，我们可以使用双指针 left 和 right。如果 nums₁ 的首个元素可以增加「优势」，就配对 left 对应的元素并向右移动一个位置；如果无法配对，就配对 right 对应的元素并向左移动一个位置。

代码：

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();vector<int> idx1(n), idx2(n);iota(idx1.begin(), idx1.end(), 0);iota(idx2.begin(), idx2.end(), 0);sort(idx1.begin(), idx1.end(), [&](int i, int j) { return nums1[i] < nums1[j]; });sort(idx2.begin(), idx2.end(), [&](int i, int j) { return nums2[i] < nums2[j]; });vector<int> ans(n);int left = 0, right = n - 1;for (int i = 0; i < n; ++i) {if (nums1[idx1[i]] > nums2[idx2[left]]) {ans[idx2[left]] = nums1[idx1[i]];++left;}else {ans[idx2[right]] = nums1[idx1[i]];--right;}}return ans;}
};

执行用时：176 ms, 在所有 C++ 提交中击败了28.28%的用户
内存消耗：58.3 MB, 在所有 C++ 提交中击败了83.02%的用户
复杂度分析
时间复杂度： O(nlogn)，其中 n 是数组 nums₁ 和 nums₂ 的长度，即为排序需要的时间。
空间复杂度： O(n)，即为排序时存储下标需要的空间。
author：LeetCode-Solution