My solutions, what's the time complexity?


  • 0
    S
    class Solution {
    public:
        vector<int> maxNumber(vector<int>& A, vector<int>& B, int k) {
            vector<int> ans;
            int a = -1, b = -1;
            int m = A.size(), n = B.size();
            for (int c = 0; c < k; c++) {
                int ea = m-1, eb = n-1;
                while (ea > a || eb > b) {
                    int i = findMaxDigit(A, a+1, ea, B, b+1, eb); //inclusive
                    if (i < m) {
                        if (m - (i + 1) + n - (b + 1) >= k - (c+1)) { // found in A
                            a = i; ans.push_back(A[i]); break;
                        } else {
                            ea = i - 1;
                        }
                    } else {
                        i -= m;
                        if (m - (a + 1) + n - (i + 1) >= k - (c+1)) { // found in B
                            b = i; ans.push_back(B[i]); break;
                        } else {
                            eb = i - 1;
                        }
                    }
                }
            }
            return ans;
        }
        int findMaxDigit(vector<int>& A, int sa, int ea, vector<int>& B, int sb, int eb) // inclusive
        {
            int max = INT_MIN, pos = -1;
            for (int i = sa; i <= ea; i++) {
                if (A[i] > max) {
                    max = A[i];
                    pos = i;
                }
            }
            for (int i = sb; i <= eb; i++) {
                if (B[i] > max) {
                    max = B[i];
                    pos = i + A.size();
                }
            }
            return pos;
        }
    };

  • 0
    E

    this solution is not cover all

    example

    [3,9,5]
    [8,9,9]
    5

Log in to reply
 

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