C++ solution, runtime O(n), in-place, easy to understand


  • 22
    J

    The idea is to go from the last indexes of both arrays, compare and put elements from either A or B to the final position, which can easily get since we know that A have enough space to store them all and we know size of A and B. Please refer to the comments for details.

    class Solution {
    public:
        void merge(int A[], int m, int B[], int n) {
            
            int a=m-1;
            int b=n-1;
            int i=m+n-1;    // calculate the index of the last element of the merged array
            
            // go from the back by A and B and compare and put to the A element which is larger
            while(a>=0 && b>=0){
                if(A[a]>B[b])   A[i--]=A[a--];
                else            A[i--]=B[b--];
            }
            
            // if B is longer than A just copy the rest of B to A location, otherwise no need to do anything
            while(b>=0)         A[i--]=B[b--];
        }
    };

  • 1
    J

    Why havent you checked the condition if A is longer than B and all the elements in array A are iterated and the only remaining is the elements in B.. in that case shouldnt you add an extra while loop like you did for B


  • 0
    L

    the situation you described will fall into the second wile loop, because when all the elements in A are iterated, it will get out of the first wile loop, then second loop will be executed.


  • 0
    J

    jayasuryajeyakodi, to answer your question "Why havent you checked the condition if A is longer than B ", problem description says "You may assume that A has enough space". So from the beginning I know that I need to put all elements in A.


  • 0
    W

    @JackBauer i have a question:

    for A is 1000, 1001, 10002, 1003, 1004, 1005, but for B is 1, 2. I think your solution is wrong for this case.


  • 0
    D
    This post is deleted!

Log in to reply
 

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