优势洗牌 图解题解

这道题到底在问什么

输入

nums1=[2,7,11,15], nums2=[1,10,4,11]

输出

[2,11,7,15]（优势=4）

最优解：一步一步想明白

1. 3口诀:能赢就赢、赢不了就用最弱的去送。下面每帧都在套它。
2. 4这是我方马的原始顺序,乱的。第一步先把它们从弱到强排序,方便「先派弱马」。
3. 5我方马排好了,从弱到强是 [ 2, 5, 9, 11, 14, 20 ]。最弱的 2 排最前,最强的 20 排最后。
4. 6这是对手马,顺序是固定的,因为答案要一一对位。我们要记住每匹对手马的原始位置,赢谁、送谁都要把我方马填回对手那个位置上。
5. 7把对手也从弱到强排一份(原始位置另记着)。架两个指针:i 指对手当前最弱的马、j 指当前最强的马,从两头往中间夹。答案数组 ans 先全空着。
6. 8开战!两队都从弱到强排好,对手两端架上 i、j 指针。我方按从弱到强的顺序一匹匹上场,第一匹是最弱的 2。
7. 9轮到我方目前最弱的马 2(侧栏高亮)。先看对手当前最弱的马 6。2 连对手最弱的 6 都赢不了,说明它谁也赢不了。既然是废棋,就拿去送给对手最强的马。
8. 10把 2 送给对手最强的 19(它的原始位置 3),这场我们认输、标红,但用一匹废马换掉了对手的王牌。j 左移,下次对手的「最强」就换成更小的了。ans 第 3 位填上 2。
9. 11轮到我方目前最弱的马 5(侧栏高亮)。先看对手当前最弱的马 6。5 连对手最弱的 6 都赢不了,说明它谁也赢不了。既然是废棋,就拿去送给对手最强的马。
10. 12把 5 送给对手最强的 15(它的原始位置 5),这场我们认输、标红,但用一匹废马换掉了对手的王牌。j 左移,下次对手的「最强」就换成更小的了。ans 第 5 位填上 5。
11. 13轮到我方目前最弱的马 9(侧栏高亮)。先看对手当前最弱的马 6。9 比 6 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
12. 14成交!把 9 安排去赢对手的 6(它的原始位置 2),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 2 位填上 9。
13. 15轮到我方目前最弱的马 11(侧栏高亮)。先看对手当前最弱的马 7。11 比 7 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
14. 16成交!把 11 安排去赢对手的 7(它的原始位置 4),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 4 位填上 11。
15. 17轮到我方目前最弱的马 14(侧栏高亮)。先看对手当前最弱的马 8。14 比 8 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
16. 18成交!把 14 安排去赢对手的 8(它的原始位置 0),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 0 位填上 14。
17. 19轮到我方目前最弱的马 20(侧栏高亮)。先看对手当前最弱的马 12。20 比 12 大,能赢!那就别浪费,拿它赢下这场最划算的胜利。
18. 20成交!把 20 安排去赢对手的 12(它的原始位置 1),对手这匹标绿表示被我们赢了。i 右移,接着看对手下一个最弱的。ans 第 1 位填上 20。
19. 21全部安排完毕。绿格是我们赢下的 4 场,从左边长出来;红格是送掉的 2 场,从右边长出来,两边在中间会合。优势 = 绿格数 = 4,已经是最大值。
20. 22换个角度看我方马:绿色这几匹去赢了对手,红色这几匹是赢不了被拿去送的。注意被送的都是最弱的那几匹,强马一匹没浪费。
21. 23这就是最终的 ans。它是按对手原始位置填出来的,所以直接和原始 nums2 对位:绿表示这一位我方更大、赢了。数一数,赢的正好是 4 场。
22. 24最后回到对手的原始顺序 nums2。绿格是我方那一位更大、拿下优势的位置,一共 4 个,这就是最大优势。红格是认输的位置,已被我们的废马占着,一分没多送。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问