Share C++ 72ms with simple comments


  • 5
    L
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        const int size1 = nums1.size();
        const int size2 = nums2.size();
        if (size1 + size2 < k) return vector<int>();
        vector<int> res(k, 0);
        vector<vector<int>> dp1(k+1, vector<int>()), dp2(k+1, vector<int>());
        getDp(nums1, k, dp1);
        getDp(nums2, k, dp2);
        for (int i = 0; i <= min(k, size1); i++) {
            int j = k - i;
            vector<int> temp_res(k, 0);
            myMerge(dp1[i].begin(), dp1[i].end(), dp2[j].begin(), dp2[j].end(), temp_res.begin());
            if (j <= size2 && compareVector(temp_res, res)) {
                res = temp_res;
            }
        }
        return res;
    }
    
    template <class container>
    bool compareVector ( container vec1, container vec2)
        {
          typename container::iterator first1 = vec1.begin(), last1 = vec1.end();
          typename container::iterator first2 = vec2.begin(), last2 = vec2.end();
          while (first1 != last1 && first2 != last2) {
            if (*first1 > *first2)
              return true;
            else if (*first1 < *first2) return false;
            ++first1; ++first2;
          }
          if (first1 == last1) return false;
          else return true;
        }
        
    void getDp(vector<int> nums, int k, vector<vector<int>> &dp) {
          while (nums.size() > k) {
                int j = 0;
                for (; j < nums.size() - 1; ++j) {
                    if (nums[j] < nums[j + 1]) {
                        nums.erase(nums.begin() + j); 
                        break;
                    }
                }
                if (j == nums.size() - 1) nums.erase(nums.begin() + j); 
           }
           dp[nums.size()] = nums;
           const int size1 = nums.size();
           for (int i = k; i > 0; i--) {
            if (i >= size1) continue; 
            else {
                dp[i] = dp[i+1];
                int j = 0;
                const int size_dp = dp[i].size();
                for (; j < size_dp - 1; ++j) {
                    if (dp[i][j] < dp[i][j + 1]) {
                        dp[i].erase(dp[i].begin() + j); 
                        break;
                    }
                }
                if (j == size_dp - 1) dp[i].erase(dp[i].begin() + j); 
            }
            
        }
    }
    template <class InputIterator1, class InputIterator2, class OutputIterator>
    OutputIterator myMerge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result)
    {
      while (true) {
        if (first1==last1) return std::copy(first2,last2,result);
        if (first2==last2) return std::copy(first1,last1,result);
        if (*first2 > *first1) *result++ = *first2++;
        else if (*first2 < *first1) *result++ = *first1++;
        else { // *first1 == *first2
            auto pos1 = first1, pos2 = first2;
            while (true) {
                int f1 = (++pos1 != last1) ? *(pos1) : INT_MIN;
                int f2 = (++pos2 != last2) ? *(pos2) : INT_MIN;
                if (f1 > f2) { *result++ = *first1++; break;}
                else if (f1 < f2) {*result++ = *first2++; break;}
            }
        }
      }
    }

  • 0
    L

    You can get the maximum num during the merge process, since if the new num has bit less than the current maximum result, it can not be the maximum. This could reduce the running time to 52ms

    void mergeNumber(vector<int>& nums1, vector<int>& nums2, vector<int>& maxNum) {
        vector<int> res;
        int n1 = nums1.size(), n2 = nums2.size();
        if(n1 == 0 && n2 == 0) return;
        
        int i = 0, j = 0, pos = 0;
        bool isLarger = false;
        while(i < n1 && j < n2) {
            if(nums1[i] > nums2[j]) {
                res.push_back(nums1[i++]);
            } 
            else if(nums1[i] < nums2[j]) {
                res.push_back(nums2[j++]);
            } 
            else if(nums1[i] == nums2[j]) {
                if(i == n1-1) {
                    res.push_back(nums2[j++]);
                } 
                else if(j == n2-1) {
                    res.push_back(nums1[i++]);
                }
                else {
                    int tmp1 = i; int tmp2 = j;
                    while(nums1[tmp1+1] == nums2[tmp2+1] && tmp1 < n1-1 && tmp2 < n2-1) {
                        tmp1++; tmp2++;
                    }
                    if(nums1[tmp1+1] > nums2[tmp2+1] || tmp2 == n2-1) {
                        res.push_back(nums1[i++]);
                    } else res.push_back(nums2[j++]);
                }
            }
            
            if(!isLarger && res[pos] > maxNum[pos]) isLarger = true;
            if(res[pos] < maxNum[pos] && !isLarger) return;
            pos++;
        }
        
        while(i < n1) {
            res.push_back(nums1[i++]);
            if(!isLarger && res[pos] > maxNum[pos]) isLarger = true;
            if(res[pos] < maxNum[pos] && !isLarger) return;
            pos++;
        }
        while(j < n2) {
            res.push_back(nums2[j++]);
            if(!isLarger && res[pos] > maxNum[pos]) isLarger = true;
            if(res[pos] < maxNum[pos] && !isLarger) return;
            pos++;
        }
        
        if(isLarger) maxNum = res;
        return;
    };

  • 0
    G

    clear idea to think from the perspective of backward elimination, instead of forward selection.


  • 0
    L

    it is clever to delete the one digit to produce a largest number for the remain digits


Log in to reply
 

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