leetcode 321. Create Maximum Number 根据两个整数创造一个有k位的最大的数 + 贪心算法

ゝ一世哀愁。 2022-06-07 01:08 129阅读 0赞

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.

Example 1:  
nums1 = \[3, 4, 6, 5\]  
nums2 = \[9, 1, 2, 5, 8, 3\]  
k = 5  
return \[9, 8, 6, 5, 3\]

Example 2:  
nums1 = \[6, 7\]  
nums2 = \[6, 0, 4\]  
k = 5  
return \[6, 7, 6, 0, 4\]

Example 3:  
nums1 = \[3, 9\]  
nums2 = \[8, 9\]  
k = 3  
return \[9, 8, 9\]

这道题给了我们两个数组，里面数字是无序的，又给我们一个k值为k <= m + n，然后我们从两个数组中共挑出k个数，数字之间的相对顺序不变，求能组成的最大的数。

这道题，说实话，我自己肯定想不出来的，这是网上看的做法。

建议和[leetcode 402. Remove K Digits 贪心算法 + DFS深度优先遍历 + stack][leetcode 402. Remove K Digits _ _ DFS_ _ stack] 和 [leetcode 738. Monotone Increasing Digits 最大单调递增数字一起学习][leetcode 738. Monotone Increasing Digits]

代码如下：

import java.util.Arrays;
    import java.util.Stack;
    
    /*
     * 这个题也需要反思，贪心算法
     * http://blog.csdn.net/yzhang6_10/article/details/51367533
     * http://blog.csdn.net/zly9923218/article/details/51014902
     * 1）分别从nums1(长度为m）和nums2（长度为n）中挑选出i（max(0, k - n) <= i <= min(m, k) 和k-i个数，
     * 在保持挑选数组的元素相对顺序不变的情况下，使选出的子数组最大化，主要利用贪心算法进行选取；
     * 2）在保持元素相对位置不变的前提下，将数组nums1与nums2合并，使合并的数组最大化。
     * */
    class Solution 
    {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) 
        {
            int[] result=new int[k];
            Arrays.fill(result, 0);
            if(nums1==null || nums2==null)
                return result;
    
            //根据  k-i<=nums2.length && k-i>=0 推导出来的
            for(int i=Math.max(0, k-nums2.length); i<=k && i<=nums1.length;i++)
            {
                int[] result1 = findKMaxNum(nums1,i);
                int[] result2 = findKMaxNum(nums2,k-i);
                int a=0,b=0,c=0;
                int[] tmp=new int[k];
    
                //归并
                while(a<result1.length || b<result2.length)
                    tmp[c++] = cmp(result1,a,result2,b)? result1[a++] : result2[b++];
    
                if(cmp(tmp,0,result,0))
                    result=tmp;         
            }
            return result;
        }
    
        //比较
        private boolean cmp(int[] num1, int i, int[] num2, int j) 
        {
            for(;i<num1.length && j<num2.length;i++,j++)
            {
                if(num1[i]>num2[j])
                    return true;
                else if(num1[i]<num2[j])
                    return false;
            }
            //这个是为了考虑到越界的情况
            if(i<num1.length)
                return true;
            else 
                return false;
        }
    
        /*  
         * 使用栈得到最大的k个值，同时要保留相关的次序
         * 这里是使用数组模拟栈
        */
        public int[] findKMaxNum1(int[] nums, int k) 
        {
            int[] reslut=new int[k];
            int size=0;
            for(int i=0;i<nums.length;i++)
            {
                while(size>0 && nums.length-i > k-size && reslut[size-1]<nums[i])
                    size--;
    
                if(size<k)
                    reslut[size++]=nums[i];
            }
            return reslut;
        }
    
    
        /*
         * 这是使用栈来实现
         * */
        public int[] findKMaxNum(int[] nums, int k) 
        {
            int[] reslut=new int[k];
            Stack<Integer> stack=new Stack<>();
            for(int i=0;i<nums.length;i++)
            {
                while(stack.isEmpty()==false && nums.length-i > k-stack.size()  && stack.peek()<nums[i])
                    stack.pop();
    
                if(stack.size()<k)
                    stack.push(nums[i]);
            }
            for(int i=reslut.length-1;i>=0;i--)
                reslut[i]=stack.pop();
            return reslut;
        }
    }

下面是C++的做法，就这么做吧，要是遇到这样的题，感觉做不出来

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    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;
        }
    };

[leetcode 402. Remove K Digits _ _ DFS_ _ stack]: http://blog.csdn.net/jackzhang_123/article/details/78743050
[leetcode 738. Monotone Increasing Digits]: http://blog.csdn.net/jackzhang_123/article/details/78894361