O(1) space solution


  • 0
    W

    take use of nums2, to avoid allocate another array to hold the result, produces an O(1) space, but O(m * n) time solution:

    func merge(nums1 []int, m int, nums2 []int, n int) {
        if n == 0 {
            return
        }
    	i := 0
    	for i < m {
    		if nums1[i] <= nums2[0] {
    			i++
    			continue
    		}
    		//nums1[i] > nums2[j]
    		nums1[i], nums2[0] = nums2[0], nums1[i]
    
    		for k := 1; k < n && nums2[k] < nums2[k-1]; k++ {
    			nums2[k], nums2[k-1] = nums2[k-1], nums2[k]
    		}
    	}
    
    	for j := 0; j < n; j++ {
    		nums1[m+j] = nums2[j]
    	}
    }
    

Log in to reply
 

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