Anything wrong with the algorithm?


  • 1
    Y

    //The major algorithm for my code is to start comparison from the end of the A array (A[m+n-1]) so that the other elements in A will not be covered. It compares the largest elements of the two arrays, and put the largest one into the end. Here are the codes, any one know why there is a problem in the solution?

    void merge(int A[], int m, int B[], int n) {

        int posA = m-1;
    
        int posB = n-1;
    
        int i = m+n-1;
    
        while(i>=0)
    
        {
    
            if(A[posA]<=B[posB]&&posB>=0)
    
            {
    
                A[i--]=B[posB--];
    
            }
            else if(A[posA]>B[posB]&&posA>=0)
            {
    
                A[i--]=A[posA--];
            }
    

    //If elements in A[] is all selected and removed, there will be no comparison
    //Just remove then to the right place

            if(posA==-1&&posB>=0){
    
                A[i--]=B[posB--];
    
            }
    
        }
    
    }

  • 0
    Y

    void merge(int A[], int m, int B[], int n) {
    int i = m+n-1;
    int posA = m-1;
    int posB = n-1;

        while(posB>=0)
        {
            if(posA==-1)
                A[i--]=B[posB--];
            
            else if(A[posA]<=B[posB])
            {
                A[i--]=B[posB--];
            }
            else if(A[posA]>B[posB])
            {
                A[i--]=A[posA--];
            }
        }
    }

Log in to reply
 

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