Why is my solution TLE? I just use the most common mergesort


  • 0
    J
    public class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int[] nums3 = new int[m + n];
            if(m == 0){
                for(int i = 0; i < n; i ++){
                    nums1[i] = nums2[i];
                }
                return;
            }
            if(n == 0) return;
            int l = 0;
            int r = 0;
            int index = 0;
            while(l < m && r < n){
                if(nums1[l] <= nums2[r]){
                    nums3[index] = nums1[l];
                    l ++;
                    index ++;
                }
                else{
                    nums3[index] = nums2[r];
                    index ++;
                    r ++;
                }
            }
            while(l < m){
                for(int j = l; j < m && index < m + n; j ++){
                    nums3[index] = nums1[j];
                    index ++;
                }
            }
            while(r < n){
                for(int j = r; j < n && index < m + n; j ++){
                    nums3[index] = nums2[j];
                    index ++;
                }
            }
            for(int i = 0; i < m + n; i ++){
                nums1[i] = nums3[i];
            }
        }
    }

  • 2
    R

    Good one. But I suggest you to optimize it further by not using nums3 array.

    Coming to the error with the solution, it is too simple thing to escape your eye. After the comparison while loop, you used two more while loops for copying array values into the nums3 array. And you used for loops in the while loops. So, at run time, the while loops never break, as they have conditions on l and m, and r and n, which remain constant throughout the execution of the for loop. So, these two while loops never end.

    We don't actually need while loops here, because for loop does the job for you. So, just change the while loops to if loops. The solution will get accepted.

    So the solution will be,

    Change

    while(l < m){
        for(int j = l; j < m && index < m + n; j ++){
            nums3[index] = nums1[j];
            index ++;
        }
    }
    while(r < n){
        for(int j = r; j < n && index < m + n; j ++){
            nums3[index] = nums2[j];
            index ++;
        }
    

    to

    if(l < m){
        for(int j = l; j < m && index < m + n; j ++){
            nums3[index] = nums1[j];
            index ++;
        }
    }
    if(r < n){
        for(int j = r; j < n && index < m + n; j ++){
            nums3[index] = nums2[j];
            index ++;
        }

  • 0
    J

    thanks!Correct answer!


Log in to reply
 

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