My solution in O(n) time, and the idea is sort the array from right to left


  • 2

    This is my solution, the thought is sort the array from right to left. What calls for special attention is that when B is empty, break the FOR loop, when A is empty, just copy the rest of the B to A.

    class Solution {
    public:
        void merge(int A[], int m, int B[], int n) {
            int  p = m - 1, q = n - 1;
            for (int i = m + n - 1; i >= 0; --i)
    			if (p >= 0 && q >= 0)
    				A[i] = A[p] > B[q] ? A[p--] : B[q--];
    			else if (q >= 0)
    				A[i] = B[q--];
    			else
    				break;
        }
    };

Log in to reply
 

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