LeetCode 870 Advantage Shuffle

Tag: 数组类题目 LeetCode Posted on 2022-02-13 14:28:41 Edited on 2022-02-13 14:44:22 Views: 170

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/