[1,2,3] [4,5,6] got Run Time Error but runs well on VS


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

  • 1
    S

    You should explain your idea so that people can understand your code faster and better. Anyway it is easy to spot at least one bug:

    for(int i=m+n;i>a+1;i--)
            A[i]=A[i-1];
    

    So basically you are trying to access A[m+n] in the first iteration, whereas A is only guaranteed to hold m+n elements.

    BTW, the running time of your code is O(n^2) in the worse case. Also you should not use anything like 'A[a]==0' to test if A[a] is empty, since 0 is not necessary a special value.

    A better idea might be to scan A and B from backwards, and merge the two arrays in a 'reverse descending' order (== ascending order). That way you do not need to worry about inserting an element to a place already occupied by other values.


  • 0
    Z

    Backwards solution works, thank you!


Log in to reply
 

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