Can it be done without creating a new merged array, meaning sorting using only B and A?


  • 3
    A

    Can it be done without creating a new merged array, meaning sorting using only B and A?


  • 11

    Yes, you are suppose to merge B into A without using any extra space.


  • 0
    A

    That was easy if you think out of the box - in reverse :)


  • 0
    H

    of course, you can just copy B into A, from end to the start

    if you're familiar with STL, you can refer to the method of rbegin iterator


  • 26
    R

    yes, you can do this at runtime:

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

  • 2
    D

    Yes, Try solve it by fill proper int to array A's tail first.


  • 5
    E
    class Solution {
    public:
        void merge(int A[], int m, int B[], int n) {
            
            auto posA = m - 1;
            auto posB = n - 1;
            auto posWrite =  n + m - 1;
            
            while (posB >= 0 && posA >= 0) {
                if (B[posB] < A[posA])
                    A[posWrite--] = A[posA--];
                else
                    A[posWrite--] = B[posB--];
            }
                
            for (; posB >= 0; --posWrite, --posB)
                A[posWrite] = B[posB];
        }
    };

  • 0
    S

    Answers you've written should describe your code with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    R
    This post is deleted!

  • 0
    J
    public void merge(int A[], int m, int B[], int n) {
            int index=m+n-1;
            for(int i=m-1,j=n-1;index>=0;index--) {
                if(i>=0&&j>=0) {
                    if(B[j]>A[i]) 
                        A[index] =B[j--];
                    else 
                        A[index] =A[i--];
                } else {
                    if(j>i) 
                        A[index] =B[j--];
                    else 
                        A[index] =A[i--];
                    
                }
            } 
    }

  • 1
    D

    My solution is almost the same way as those above. Merge from the end. Take care if A[] or B[] is used up. Let me finish it in one line:

        void merge(int A[], int m, int B[], int n) {
            for(int i=m+n-1;i>=0;i--) A[i]=(m!=0&&(n==0||A[m-1]>B[n-1]))?A[--m]:B[--n];
        }

  • 0
    R
    public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        
        int total;
        int lengthA=m-1;
        int lengthB=n-1;
        
        for (total=m+n-1;total>=0;total--){
            if (lengthA<0){
                 A[total]=B[lengthB--];
            }else if (lengthB<0){
                A[total]=A[lengthA--];
            }else if (A[lengthA]>=B[lengthB]){
                A[total]=A[lengthA--];
                //lengthA--;
            }else {
                A[total]=B[lengthB--];
                //lengthB--;
            }
        }
        
    }
    

    }


  • 0
    K
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 4
    K

    Look at my in-place merging from the tail of A. I believe it is both simple and easy to understand.

    public class Solution {
        public void merge(int A[], int m, int B[], int n) {
            while(m>0 && n>0)
                A[m+n-1] = A[m-1] > B[n-1] ? A[--m] : B[--n];
            while(n>0)
                A[n-1] = B[--n];
        }
    }

  • 0
    G

    Could be further simplified using one single loop:

    public class Solution {
    	public void merge(int A[], int m, int B[], int n) {
    		while ( n>0){
    				A[m+n-1] = (m<=0 || A[m-1]< B[n-1] )? B[--n] : A[--m];
    		}
    	}
    }

  • 1
    G

    Could be further simplified by using one single loop:

    public class Solution {
        public void merge(int A[], int m, int B[], int n) {
            while (n>0){
                A[m+n-1] = (m<=0 || A[m-1]< B[n-1] )? B[--n] : A[--m];
            }
        }
    }
    

  • 0
    W

    It can be accepted in OJ, yet I think it'll be wrong when B[] is over (n = 0) firstly, the remaining elements in B[] wouldn't be merged into A[]. Right?


  • 0
    R
    This post is deleted!

Log in to reply
 

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