0870. 优势洗牌【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心（田忌赛马）

1. 📝 题目描述

• leetcode

给定两个长度相等的数组 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 <= 10^5
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 10^9

2. 🎯 s.1 - 贪心（田忌赛马）

c

int cmpAsc(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int* nums2Ref;
int cmpDesc(const void* a, const void* b) { return nums2Ref[*(int*)b] - nums2Ref[*(int*)a]; }

int* advantageCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int n = nums1Size;
    qsort(nums1, n, sizeof(int), cmpAsc);
    int* idx = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) idx[i] = i;
    nums2Ref = nums2;
    qsort(idx, n, sizeof(int), cmpDesc);
    int* res = (int*)malloc(sizeof(int) * n);
    int lo = 0, hi = n - 1;
    for (int k = 0; k < n; k++) {
        int i = idx[k];
        if (nums1[hi] > nums2[i]) res[i] = nums1[hi--];
        else res[i] = nums1[lo++];
    }
    free(idx);
    *returnSize = n;
    return res;
}

js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function (nums1, nums2) {
  const n = nums1.length
  nums1.sort((a, b) => a - b)
  const idx = Array.from({ length: n }, (_, i) => i).sort(
    (a, b) => nums2[b] - nums2[a],
  )
  const res = new Array(n)
  let lo = 0,
    hi = n - 1
  for (const i of idx) {
    if (nums1[hi] > nums2[i]) res[i] = nums1[hi--]
    else res[i] = nums1[lo++]
  }
  return res
}

py

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        nums1.sort()
        idx = sorted(range(n), key=lambda i: -nums2[i])
        res = [0] * n
        lo, hi = 0, n - 1
        for i in idx:
            if nums1[hi] > nums2[i]:
                res[i] = nums1[hi]
                hi -= 1
            else:
                res[i] = nums1[lo]
                lo += 1
        return res

• 时间复杂度：$O(n\log n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 将 nums1 升序排列，nums2 的索引按值降序排列
• 对 nums2 中最大的元素，若 nums1 最大值能赢则匹配，否则用 nums1 最小值浪费