中等

问题描述

给定两个大小相等的数组 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 <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 109

贪心

创建两个数组 $idx1$ 和 $idx2$ 分别用于记录 $nums1$ 和 $nums2$ 各个数字的下标，然后对 $idx1$ 和 $idx2$ 按 $nums1$ 和 $nums2$ 从小到大进行排序，得到 $nums1$ 和 $nums2$ 从小到大排序后的下标序列。

使用 $left$ 和 $right$ 两个指针分别指向 $idx2$ 的头部和尾部，遍历 $idx1$

• 当 $nums1[idx1[i]] > nums2[idx2[left]]$ 时，$nums1$ 中第 $i$ 小的数对当前尚未匹配的 $nums2$ 最小的数有优势，将 $idx2[left]$ 位置的值置为 $nums1[idx1[i]]$，然后 $left$ 指针右移。
• 当 $nums1[idx1[i]] <= nums2[idx2[left]]$ 时，$nums1$ 中第 $i$ 小的数对 $nums2$ 中尚未匹配的数都无任何优势，因此，将其与 $nums2$ 中尚未匹配的最大数进行匹配，即将 $idx2[right]$ 位置的值置为 $nums1[idx1[i]]$，然后 $right$ 指针左移。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function (nums1, nums2) {
  const n = nums1.length
  const idx1 = new Array(n).fill(0)
  const idx2 = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    idx1[i] = i
    idx2[i] = i
  }
  idx1.sort((i, j) => nums1[i] - nums1[j])
  idx2.sort((i, j) => nums2[i] - nums2[j])
  let ans = new Array(n)
  let left = 0
  let right = n - 1
  for (let 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
}

• 时间复杂度：$O(n \log {n})$
• 空间复杂度：$O(n)$