92ms cpp: try first biggest num, with index pre-process


  • 2
    W

    The basic idea is to find the largest number in answer array's first position: try number from 9 to 0, firstly in nums1: if a number can be found, check if the left numbers (minus numbers before the found number) are sufficient for k.

    If we can find a largest number in both nums1 and nums2, we should compare the two answers, and keep the bigger one.

    A fast pre-process for above solution: for i-th element in array nums1, lowPos1[i][num] is the smallest index of num in range [i, nums1.size()-1]. Since we have this helper, we can use O(1) time to find if num exists in nums1 or nums2 from a given position.

    An important special case: when nums1.size() + nums2.size() = k, which means we have to use all elements in both arrays to produce the k-length answer. In such case, set two pointers pointing to the beginning of two arrays. Move the pointer with bigger number. Tricky part is when two pointers point to a same value, in this case we detect the values in two arrays behind the two pointers; we move the two pointers together until we find the values are different or one array is ended. The pointer with bigger value should go first, and if one pointer gets to end of array, the other pointer should go first.

    class Solution {
    public:
        unordered_map<string, vector<int>> store;
        deque<vector<int>> lowPos1, lowPos2;
        int len1, len2;
        
        vector<int> get(int p1, int p2, int k, vector<int>& nums1, vector<int>& nums2) {
            vector<int> ans;
            if (k==0)
                return ans;
            
            char buf[50];
            sprintf(buf, "%d.%d.%d", p1, p2, k);
            string key = buf;
            if (store.find(key) != store.end())
                return store[key];
            
            int rest = nums1.size()-p1 + nums2.size()-p2;
            if (k==rest) {
                while (p1<len1 || p2<len2)
                {
                    if (p1==len1 || (p2<len2 && nums1[p1] < nums2[p2]))
                        ans.push_back(nums2[p2++]);
                    else if (p2==len2 || (p1<len1 && nums1[p1] > nums2[p2]))
                        ans.push_back(nums1[p1++]);
                    else {
                        int i=0;
                        while (p1+i<len1 && p2+i<len2) {
                            if (nums1[p1+i] != nums2[p2+i])
                                break;
                            i++;
                        }
                        if (p1+i==len1 || (p2+i<len2 && nums2[p2+i]>nums1[p1+i]))
                            ans.push_back(nums2[p2++]);
                        else
                            ans.push_back(nums1[p1++]);
                    }
                }
            }
            else
            {
                for (int i=9; i>=0; i--) 
                {
                    vector<int> ans1, ans2;
                    int j = p1==len1 ? -1 : lowPos1[p1][i];
                    if (j!=-1 && rest-(j-p1)-1 >= k-1)
                    {
                        ans1.push_back(i);
                        vector<int> temp = get(j+1, p2, k-1, nums1, nums2);
                        ans1.insert(ans1.end(), temp.begin(), temp.end());
                    }
                    
                    j = p2==len2 ? -1 : lowPos2[p2][i];
                    if (j!=-1 && rest-(j-p2)-1 >= k-1)
                    {
                        ans2.push_back(i);
                        vector<int> temp = get(p1, j+1, k-1, nums1, nums2);
                        ans2.insert(ans2.end(), temp.begin(), temp.end());
                    }
        
                    if (ans1.size() + ans2.size())
                    {
                        if (ans1.size() < ans2.size())
                            std::swap(ans1, ans2);
                        bool use1=true;
                        for (int i=0; i<min(ans1.size(), ans2.size()); i++)
                            if (ans2[i] != ans1[i]) {
                                use1 = ans1[i]>ans2[i];
                                break;
                            }
                        ans = use1 ? ans1 : ans2;
                        break;
                    }
                }
            }
            
            store[key] = ans;
            return ans;
        }
        
        void preProcess(deque<vector<int>>& lowPos, const vector<int>& nums) {
            lowPos.push_back(vector<int> (10, -1));
            for (int i=(int)nums.size()-1; i>=0; i--) {
                lowPos.push_front(lowPos.front());
                lowPos.front()[nums[i]] = i;
            }
            lowPos.pop_back();
        }
        
        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            len1=nums1.size(), len2=nums2.size();
            preProcess(lowPos1, nums1);
            preProcess(lowPos2, nums2);
            
            return get(0, 0, k, nums1, nums2);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.