优势洗牌 图解题解

优势洗牌要我们排出什么顺序

给两个等长数组 nums1 和 nums2。把 nums1 重新排一个顺序，让 nums1[i] ＞ nums2[i] 成立的位置尽量多，这个「我方在多少位上更大」的个数就叫优势。nums2 不动，只有 nums1 能调。题面 nums1=[2,7,11,15]、nums2=[1,10,4,11] 时，最好的排法之一是 [2,11,7,15]，四个位置全部我方更大，优势 4。

把所有排列都试一遍为什么根本跑不动

把 nums1 的每种排列都摆出来、逐一数优势、留最大的，是照定义写的笨办法。但 n 个数有 n! 种排列，n 才 10 就三百多万种、20 就是天文数字，光枚举就卡死。这条路只有 n 是个位数时能走，题目规模下完全不现实。

田忌赛马的老主意怎么搬到这道题上

田忌赛马讲的是：自己的马从弱到强排好，对手的也从弱到强看。轮到我方当前最弱的一匹，先跟对手当前最弱的比。能赢就赢下这场最省力的胜利；连对手最弱都赢不了，这匹就是废棋，与其浪费，不如拿去对付对手最强那匹。反正要输一场，就用最弱的去输、把能打的省下来赢别人。赢的判定是严格大于：相等不算优势，题目要的是 nums1[i] ＞ nums2[i]。

两个指针怎么夹，答案又怎么填回原位

先给 nums1 排序；再把 nums2 连同原始下标打包排序（存成 (值, 原下标) 配对），排完序仍知道每匹对手马原本站哪一位。给对手排好的数组架两个指针，一个指最弱、一个指最强，从两头往中间夹。从弱到强遍历 nums1 每匹马 v：赢不了对手最弱那匹（v ≤ 对手最弱的值），就填进对手最强那匹的原始下标、最强指针左移；能赢就填进最弱那匹的原始下标、最弱指针右移。为什么非记原始下标？答案要和原 nums2 一一对位，排序打乱了位置，得把每匹马填回对手原本站的那格。

[2,7,11,15] 配对手，两指针把答案填回原位

nums1 排序后仍是 [2,7,11,15]。把 nums2=[1,10,4,11] 打包排序，按值升序排成 (1,0)、(4,2)、(10,1)、(11,3)，最弱指针指 (1,0)、最强指针指 (11,3)，ans 四格全空。逐匹上场：2 ＞ 对手最弱 1，能赢，填进原下标 0；7 ＞ 剩下的最弱 4，填进原下标 2；11 ＞ 10，填进原下标 1；15 ＞ 11，填进原下标 3。填完得 ans=[2,11,7,15]，优势 4。这个例子四场全赢，「赢不了就送去垫」那支没触发；想看它发威，去动画换个更胶着的例子。

相等也当赢，优势会凭空多算几场

复杂度上，两次排序是瓶颈 O(n log n)，双指针只扫一趟 O(n)；空间 O(n)，用在存对手的 (值, 原下标) 配对和答案数组。几个容易写反的地方：判赢是严格大于，若相等也算赢，优势会多算几场；赢不了时废马要送给对手当前最强那匹，随手丢给最弱的，就白扔一次本能赢的机会；排序前若没把原始下标打包，填答案时就不知道该塞回哪格，对位全乱。边界上，全部能赢时最强指针不动、最弱指针走到底；全赢不了时反过来；只剩一个元素时比一次，要么赢要么送，都对。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
    }
};

Java

import java.util.*;
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;
    }
}