LeetCode 870 Advantage Shuffle

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-13 14:28:41
    编辑于：2022-02-13 14:44:22
    浏览量：816

概述

https://leetcode.com/problems/advantage-shuffle/

暴力穷举法

穷举 nums1 的所有可能，可能数为 n! / r1! / r2! ... / rn!，n 为元素个数，r 为重复元素的个数。

孙膑法

https://labuladong.gitee.io/algo/2/21/64/

首先对两个数组降序排序，如果 nums1[i] 比 nums2[i] 打，则一局占优，否则就换用最小值输掉该局。

要注意的是我们需要对 nums2 的原始索引进行保存。

时间复杂度 O(nlogn)，因为需要排序。

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.rbegin(), nums1.rend());
        vector<pair<int, int>> nums2i;
        for (int i = 0; i < nums2.size(); i ++) nums2i.push_back({nums2[i], i});
        sort(nums2i.rbegin(), nums2i.rend());
        vector<int> ans = nums1;
        for (int i = 0, j = 0, last = nums1.size() - 1; j < nums2i.size(); j ++) {
            if (nums1[i] > nums2i[j].first) {
                ans[nums2i[j].second] = nums1[i++];
            } else {
                ans[nums2i[j].second] = nums1[last--];
            }
        }
        return ans;
    }
};

Links: leetcode-870-advantage-shuffle