A solution with O(n) time complexity and in place merge


  • 0
    N

    The idea is to use the reserved space in A to create a new array A1 = A + n. Then merge A1 and B into A.

    void merge(int A[], int m, int B[], int n) {
    	for (int i = m - 1; i >= 0; --i)
    	{
    		A[i + n] = A[i];
    	}
    
    	int a = 0;
    	int b = 0;
    	for (int i = 0; i < m + n; ++i)
    	{
    		if ((b >= n) || ((a < m) && (A[n + a] < B[b])))
    		{
    			A[i] = A[n + a];
    			a++;
    		}
    		else
    		{
    			A[i] = B[b++];
    		}
    	}
    }

Log in to reply
 

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