About 200ms Java solution, any improvement?


  • 0
    S
    public class Solution {
        public void merge(int A[], int m, int B[], int n) {
            int ptrA = m-1;
            int ptrB = n-1;
            int tmp = 0;
    
            if(n == 0) {
                A = A;   
            } else if(m == 0) {
                for(int i=0; i<n; i++) {
                    A[i] = B[i];
                }
            } else if(A[m-1] <= B[0]) {
                for(int i=m; i<m+n; i++) {
                    A[i] = B[i-m];
                }
            } else {
                tmp = A[ptrA];
                while(ptrB >= 0) {
                    if(tmp >= B[ptrB] && ptrA >= 0) {
                        A[ptrA+ptrB+1] = A[ptrA];
                        A[ptrA] = Integer.MIN_VALUE;
                        ptrA--;
                        if(ptrA < 0) {
                            tmp = Integer.MIN_VALUE;
                        } else {
                            tmp = A[ptrA];
                        }
                    } else {
                        A[ptrA+ptrB+1] = B[ptrB];
                        ptrB--;
                    }
                }
            }
        }
    }

  • 4
    S

    Mine is more concise, but also ~200ms

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

Log in to reply
 

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