[LintCode] Create Maximum Number 创建最大数

简介:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
Have you met this question in a real interview?
Example
Given nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5
return [9, 8, 6, 5, 3]
Given nums1 = [6, 7], nums2 = [6, 0, 4], k = 5
return [6, 7, 6, 0, 4]
Given nums1 = [3, 9], nums2 = [8, 9], k = 3
return [9, 8, 9]

LeetCode上的原题,请参见我之前的博客Create Maximum Number

class Solution {
public:
    /**
     * @param nums1 an integer array of length m with digits 0-9
     * @param nums2 an integer array of length n with digits 0-9
     * @param k an integer and k <= m + n
     * @return an integer array
     */
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res;
        int m = nums1.size(), n = nums2.size();
        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            res = max(res, mergeVec(maxVec(nums1, i), maxVec(nums2, k - i)));
        }
        return res;
    }
    vector<int> maxVec(vector<int> nums, int k) {
        if (k == 0) return {};
        vector<int> res;
        int drop = nums.size() - k;
        for (auto a : nums) {
            while (drop && res.size() && res.back() < a) {
                res.pop_back();
                --drop;
            }
            res.push_back(a);
        }
        res.resize(k);
        return res;
    }
    vector<int> mergeVec(vector<int> nums1, vector<int> nums2) {
        vector<int> res;
        while (nums1.size() + nums2.size()) {
            vector<int> &t = nums1 > nums2 ? nums1 : nums2;
            res.push_back(t[0]);
            t.erase(t.begin());
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:创建最大数[LintCode] Create Maximum Number ,如需转载请自行联系原博主。

相关文章
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
97 0
LeetCode 414. Third Maximum Number
|
算法
LeetCode 321. Create Maximum Number
给定长度分别为 m 和 n 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
77 0
LeetCode 321. Create Maximum Number
|
Oracle 关系型数据库 Linux
Oracle 数据库设置最大进程数参数方法,oracle最大进程数满了处理方法,sysdba管理员登录报“maximum number of processes (150) exceeded“问题解决
Oracle 数据库设置最大进程数参数方法,oracle最大进程数满了处理方法,sysdba管理员登录报“maximum number of processes (150) exceeded“问题解决
1178 0
Oracle 数据库设置最大进程数参数方法,oracle最大进程数满了处理方法,sysdba管理员登录报“maximum number of processes (150) exceeded“问题解决
|
存储 算法
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
|
Java 数据安全/隐私保护
[LintCode] Number of Islands(岛屿个数)
描述 给一个01矩阵,求不同的岛屿的个数。 0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 样例 在矩阵: [ [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1] ] 中有 3 个岛。
1252 0
Exceeded maximum number of retries. Exceeded max scheduling attempts 3 for instance 7d90eb80-29e2-4238-b658-ade407ff9456. Last exception: [u&#39;Trace
Exceeded maximum number of retries. Exceeded max scheduling attempts 3 for instance 7d90eb80-29e2-4238-b658-ade407ff9456.
1250 0
|
数据安全/隐私保护
passwd: Have exhausted maximum number of retries for service
使用命令passwd修改密码时,遇到如下问题: # echo 'utf8'|passwd zhangsan --stdin Changing password for user zhangsan.
4194 0