Share a C++ solution of 64ms


  • 0
    Y

    Most of the ideas are similar as the usual. Reduce it to two simpler questions:

    1 Create a maximal number by selecting k numbers from a single array A[]. Say the output is stored in a vector<int>, Res.

    2 Merge two numbers to create the maximal numbers.

    Both of questions can be solved by greedy algorithms, but the proofs are a little subtle.

    For question 1, we use the following idea saving memory. First, take out all the digit, and then repeat the following process: deleting the first local minimum. Every time, you get the best result by deleting a digit from the previous vector of candidates. Then, we store all the maxNumbers of <= k digits. The worst case time complexity is O(n^2). The following algorithm I used is adapted to improve the time complexity to O(k*n) and the space complexity is O(k^2).

    In fact, one can also prove that this greedy algorithm is correct.

    For question 2, the idea is like merge sort. However, the tricky step is if two leading digits are equal, we have to compare their successors. Thanks for the ideas by the other Questions on Leetcode. The worst case time complexity is O(k^2).

    Thus the worst time complexity is O(min(k^3, kn)) and space complexity is O(k^2), since every time we just maintain a number of <= k digits and we maintain totally 2k maxNumbers.

    class Solution {
               public:
         vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<int> result (k, 0);
            vector<vector<int>> maxNumbers1=maxNumbers(nums1, min(k,(int)nums1.size()));
            vector<vector<int>> maxNumbers2=maxNumbers(nums2, min((int)nums2.size(), k));
            
            for (int i=0; i<=min(k, (int)nums1.size()); i++){
                if (k-i<=min(k,(int)nums2.size())) {
                    vector<int> tem=merge(maxNumbers1[(int)maxNumbers1.size()-i-1], maxNumbers2[(int)maxNumbers2.size()-k+i-1]);
                    if (less_than(result, tem))
                    result=tem;
                }
            }
            
            return result;
        }
        
        bool less_than(vector<int>& Number1, vector<int>& Number2){
            int i=0;
            while (i<Number1.size()){
                if (Number1[i]<Number2[i]) return true;
                else if (Number1[i]>Number2[i]) return false;
                else i++;
            }
            return false;
        }
        
        vector<int> merge(vector<int>& Number1, vector<int>& Number2){
            if (Number1.size()==0) return Number2;
            if (Number2.size()==0) return Number1;
            vector<int> result;
            int i1=0, i2=0;
            while (i1<Number1.size() || i2<Number2.size()){
                if (i2==Number2.size()) {
                    result.push_back(Number1[i1]);
                     i1++;
                }else if (i1==Number1.size()){
                    result.push_back(Number2[i2]);
                    i2++;
                }
                else if (Number1[i1]<Number2[i2]){
                    result.push_back(Number2[i2]);
                    i2++;
                }else if (Number1[i1]>Number2[i2]){
                    result.push_back(Number1[i1]);
                    i1++;
                }else {
                    int k1=i1, k2=i2;
                    while (k1<Number1.size() && k2<Number2.size() && Number1[k1]==Number2[k2]) {k1++; k2++;}
                    if (k1==Number1.size() || (k2<Number2.size() && Number2[k2]>Number1[k1])) {
                        result.push_back(Number2[i2]);
                        i2++;
                    }else {
                        result.push_back(Number1[i1]);
                        i1++;
                    }
                }
            }
            return result;
        }
        
        vector<vector<int>> maxNumbers(vector<int>& nums1, int k){
            vector<vector<int>> result;
            vector<int> Number (nums1.begin(), nums1.begin()+k);
            for (int i=k; i<nums1.size(); i++){
                int j=0;
                while (j+1<k && Number[j]>=Number[j+1]) j++;
                if (j==k-1){
                    if (nums1[i]>Number[j]) Number[j]=nums1[i];
                } 
                else {
                    Number.erase(Number.begin()+j);
                    Number.push_back(nums1[i]);
                }
            }
            result.push_back(Number);
            for (int i=0; i<k; i++){
                int j=0;
                while (j+1<Number.size() && Number[j]>=Number[j+1]) j++;
                Number.erase(Number.begin()+j);
                result.push_back(Number);
            }
            
            return result;
        }
        
        
    };

  • 0
    X

    My solution is same as yours. I think it's easier to understand:

    class Solution {
    public:
        vector<int> maxNumber(vector<int>& a, vector<int>& b, int k) {
            auto at = kmax(a, max(0, k - (int)b.size()), min((int)a.size() + 1, k + 1));
            auto bt = kmax(b, max(0, k - (int)a.size()), min((int)b.size() + 1, k + 1));
            vector<int> r(k, 0);
            for (int i = max(0, k - (int)b.size()); i <= min(k, (int)a.size()); ++i) {
                auto& ap = at[i];
                auto& bp = bt[k - i];
                auto ans = makeNumber(ap, bp);
                r = max(r, move(ans));
            }
            return r;
        }
        
        vector<vector<int>> kmax(const vector<int>& v, int f, int k) {
            vector<vector<int>> r(k);
            r[k - 1] = maxNumber(v, k - 1);
            for (int i = k - 2; i >= f; --i) {
                const auto& prev = r[i + 1];
                int j = 0;
                for (; j < prev.size() - 1; ++j) 
                    if (prev[j] < prev[j + 1])
                        break;
                r[i].reserve(i);
                for (int p = 0; p < j; ++p)
                    r[i].push_back(prev[p]);
                for (int p = j + 1; p < prev.size(); ++p)
                    r[i].push_back(prev[p]);
            }
            return r;
        }
        
        vector<int> maxNumber(const vector<int>& v, int k) {
            vector<int> r;
            r.reserve(k);
            size_t i = 0;
            while (r.size() != k) {
                i = imax(v, i, v.size() - k + r.size() + 1);
                r.push_back(v[i]);
                i += 1;
            }
            return r;
        }
        
        bool vless(vector<int>& a, size_t pa, vector<int>& b, size_t pb) {
            for (; pa < a.size() && pb < b.size(); ++pa, ++pb) {
                if (a[pa] != b[pb])
                    return a[pa] < b[pb];
            }
            return a.size() - pa < b.size() - pb;
        }
        
        vector<int> makeNumber(vector<int>& a, vector<int>& b) {
            vector<int> r(a.size() + b.size());
            size_t pa = 0, pb = 0, i = 0;
            while (pa < a.size() && pb < b.size()) {
                if (vless(a, pa, b, pb))
                    r[i++] = b[pb++];
                else
                    r[i++] = a[pa++];
            }
            while (pa < a.size())
                r[i++] = a[pa++];
            while (pb < b.size())
                r[i++] = b[pb++];
            return r;
        }
        
        size_t imax(const vector<int>& v, size_t begin, size_t end) {
            end = min(end, v.size());
            size_t r = begin;
            for (auto i = begin + 1; i < end; ++i) 
                r = (v[r] >= v[i]) ? r : i;
            return r;
        }
        
        friend bool operator<(const vector<int>& lhs, const vector<int>& rhs) {
            // assert(lhs.size() == rhs.size());
            for (size_t i = 0; i < lhs.size(); ++i) {
                if (lhs[i] < rhs[i])
                    return true;
                if (lhs[i] > rhs[i])
                    return false;
            }
            return false;
        }
    };

  • 0
    H

    Modified from xinhuang's solution. Some of the code are changed to stl algorithm

    class Solution {
    public:
      vector<int> maxNumber(vector<int>& a, vector<int>& b, int k) 
      {
        if (a.size() + b.size() < k) return vector<int>(k, 0);
        if (a.size() < b.size()) return maxNumber(b, a, k);
    
        vector<int> r(k, 0);
        auto bt = kmax_until(b, k, 0);
        auto at = kmax_until(a, k, k - bt.front().size());
        auto ia = at.rbegin();
        auto ib = bt.begin();
        for (; ia != at.rend() && ib != bt.end(); ++ia, ++ib)
          r = max(r, makeNumber(*ia, *ib));
        return r;
      }
    
      vector<vector<int>> kmax_until(const vector<int>& v, int k, int until)
      {
        k = min(k, (int)v.size());
        vector<vector<int>> r{ maxNumber(v, k--) };
        while (k-- >= until)
        {
          r.push_back(r.back());
          auto first_valley = is_sorted_until(r.back().begin(), r.back().end(), greater<int>()) - 1;
          r.back().erase(first_valley);
        }
        return r;
      }
    
      vector<int> maxNumber(const vector<int>& v, int k) 
      {
        vector<int> r;
        r.reserve(k);
        for (auto iter = v.begin(), tail = v.end() - k; r.size() != k; ++iter, ++tail)
        {
          iter = max_element(iter, tail + 1);
          r.push_back(*iter);
        }
        return r;
      }
    
      vector<int> makeNumber(vector<int>& a, vector<int>& b) 
      {
        vector<int> r(a.size() + b.size());
        auto ir = r.begin(), ib = b.begin(), ia = a.begin();
        while (ia != a.end() && ib != b.end())
        {
          if (lexicographical_compare(ia, a.end(), ib, b.end())) 
            *ir++ = *ib++;
          else
            *ir++ = *ia++;
        }
        ir = copy(ia, a.end(), ir);
        ir = copy(ib, b.end(), ir);
        return r;
      }
    };

  • 0
    Y
    This post is deleted!

Log in to reply
 

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