欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

321. Create Maximum Number

程序员文章站 2022-04-25 14:42:20
...

321. Create Maximum Number

321. Create Maximum Number

这道题没想到怎么做,感觉套什么算法都套不上啊。。看了大神的答案。。果然。。这算个什么题呢,智商题。顶多算个分治吧,类似归并排序的思想。

首先,选k个数。假设在nums1里面选i个数,在nums2里面选k-i个数。枚举所有的i,把最优的结果记录下来就可以。这是大体思想。

下面是具体应该怎么做。

枚举了i然后呢?我们知道了nums1里面取i个数,必须让这i个数不打乱相对顺序的情况下最大,这样两个合并起来才最大。这样需要在nums1里面抛弃m - i个数。怎么抛弃m-i个数呢?从头遍历,如果当前遍历到的nums1[i]比当前结果集里的最后一个数大,说明用nums[i]替换掉当前结果集里的最后一个数,得到的结果集是最大的。那么就把当前结果集里的最后一个数抛弃。直到抛弃够了m-i个数。

两个nums都找到了当前最大的情况,然后把他俩合并。合并的时候就比较两个nums的第一个,谁大就把谁加到最终结果集里,直到两个nums都加完。

注意:

1. 在maxVector函数里,返回的必须是k长度的,那么如果nums是递减的,且长度大于k,那么按照上述做法得到的res肯定大于k,而且肯定一个都不会drop掉,所以必须在返回之前resize一下。

2. 在主函数里那个for循环看了好久才看明白。这个for循环的意思是这样的:我希望i表示的是从nums1里面取i个数。那么如果k特别小,小于nums1的长度,那么i可以从0开始,取到k,换句话说,我可以从nums1里面取0个,取1个,取2个。。。取k个,所以终止条件是i <= min(k, m)。那么如果k比较大,大于nums2了,那么nums2取整个数组也不够k。所以nums1至少取k-n个。所以开始条件里面的i = max(0, k - n)就是用来处理这种nums1里面最少取多少个的情况,这样小于这个数的就不用考虑了,因为一定不能取满k个数。

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> res;
        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i)));
        }
        return res;
    }
    vector<int> maxVector(vector<int> nums, int k) {
        int drop = nums.size() - k;
        vector<int> res;
        for (int num : nums) {
            while (drop && res.size() && res.back() < num) {
                res.pop_back();
                --drop;
            }
            res.push_back(num);
        }
        res.resize(k);
        return res;
    }
    vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
        vector<int> res;
        while (nums1.size() + nums2.size()) {
            vector<int> &tmp = nums1 > nums2 ? nums1 : nums2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        return res;
    }
};