Skip to content

Latest commit

 

History

History
91 lines (80 loc) · 2.26 KB

88. Merge Sorted Array.md

File metadata and controls

91 lines (80 loc) · 2.26 KB

88. Merge Sorted Array

leetcode Daily Challenge on January 11th, 2021.

Difficulty : Easy

Related Topics : Array、Two Pointers

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

  • 0 <= n, m <= 200
  • 1 <= n + m <= 200
  • nums1.length == m + n
  • nums2.length == n
  • -10^9 <= nums1[i], nums2[i] <= 10^9

Solution

  • mine
    • Java

      • Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.9 MB, less than 77.05% of Java online submissions

        // O(N)time
// O(1)space
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int e = m + n - 1;
    int i = m - 1;
    int j = n - 1;
    while(i >= 0 && j >= 0){
        if(nums1[i] >= nums2[j]){
            nums1[e--] = nums1[i--];
        }else{
            nums1[e--] = nums2[j--];
        }
    }
    while(j >= 0){
        nums1[e--] = nums2[j--];
    }
}

      • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.3 MB, less than 33.68% of Java online submissions

        // O(N)time
// O(N)space
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] res = new int[nums1.length];
    int l1 = 0, l2 = 0;
    int i = 0;
    while(l1 < m || l2 < n){
        if(l1 >= m){
            res[i++] = nums2[l2++];
        }else if(l2 >= n){
            res[i++] = nums1[l1++];
        }else{
            res[i++] = nums1[l1] <= nums2[l2] ? nums1[l1++] : nums2[l2++];
        }
    }
    for(int t = 0; t < nums1.length; t++){
        nums1[t] = res[t];
    }
}