跳转至

870. 优势洗牌

题目描述

给定两个长度相等的数组 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

解法

方法一：贪心 + 排序

类似田忌赛马。将 $nums1$, $nums2$ 按照升序排列。然后遍历 $nums1$ 中的每个元素 $v$，若在 $nums2[i..j]$ 中找不到比 $v$ 小的，则将 $v$ 与当前 $nums2[i..j]$ 中的最大元素匹配。

时间复杂度 $O(nlogn)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        t = sorted((v, i) for i, v in enumerate(nums2))
        n = len(nums2)
        ans = [0] * n
        i, j = 0, n - 1
        for v in nums1:
            if v <= t[i][0]:
                ans[t[j][1]] = v
                j -= 1
            else:
                ans[t[i][1]] = v
                i += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[][] t = new int[n][2];
        for (int i = 0; i < n; ++i) {
            t[i] = new int[] {nums2[i], i};
        }
        Arrays.sort(t, (a, b) -> a[0] - b[0]);
        Arrays.sort(nums1);
        int[] ans = new int[n];
        int i = 0, j = n - 1;
        for (int v : nums1) {
            if (v <= t[i][0]) {
                ans[t[j--][1]] = v;
            } else {
                ans[t[i++][1]] = v;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<pair<int, int>> t;
        for (int i = 0; i < n; ++i) t.push_back({nums2[i], i});
        sort(t.begin(), t.end());
        sort(nums1.begin(), nums1.end());
        int i = 0, j = n - 1;
        vector<int> ans(n);
        for (int v : nums1) {
            if (v <= t[i].first)
                ans[t[j--].second] = v;
            else
                ans[t[i++].second] = v;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func advantageCount(nums1 []int, nums2 []int) []int {
    n := len(nums1)
    t := make([][]int, n)
    for i, v := range nums2 {
        t[i] = []int{v, i}
    }
    sort.Slice(t, func(i, j int) bool {
        return t[i][0] < t[j][0]
    })
    sort.Ints(nums1)
    ans := make([]int, n)
    i, j := 0, n-1
    for _, v := range nums1 {
        if v <= t[i][0] {
            ans[t[j][1]] = v
            j--
        } else {
            ans[t[i][1]] = v
            i++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function advantageCount(nums1: number[], nums2: number[]): number[] {
    const n = nums1.length;
    const idx = Array.from({ length: n }, (_, i) => i);
    idx.sort((i, j) => nums2[i] - nums2[j]);
    nums1.sort((a, b) => a - b);

    const ans = new Array(n).fill(0);
    let left = 0;
    let right = n - 1;
    for (let i = 0; i < n; i++) {
        if (nums1[i] > nums2[idx[left]]) {
            ans[idx[left]] = nums1[i];
            left++;
        } else {
            ans[idx[right]] = nums1[i];
            right--;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn advantage_count(mut nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let n = nums1.len();
        let mut idx = (0..n).collect::<Vec<usize>>();
        idx.sort_by(|&i, &j| nums2[i].cmp(&nums2[j]));
        nums1.sort();
        let mut res = vec![0; n];
        let mut left = 0;
        let mut right = n - 1;
        for &num in nums1.iter() {
            if num > nums2[idx[left]] {
                res[idx[left]] = num;
                left += 1;
            } else {
                res[idx[right]] = num;
                right -= 1;
            }
        }
        res
    }
}

评论