Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/88.html
88. Merge Sorted Array
Level
Easy
Description
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- 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 greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Solution
To avoid overwriting elements in nums1
before the elements are put in the correct positions, start from the end of the array and put elements to the correct positions backwards.
Let index1
and index2
be indices in original arrays nums1
and nums2
, and index
be the index in merged array nums1
. Initially, index1 = m - 1
, index2 = n - 1
and index = m + n - 1
.
While both index1
and index2
are greater than or equal to 0, each time compare the elements nums1[index1]
and nums2[index2]
, and put the greater elements to nums1[index]
. Reduce index1
by 1, and reduce either index1
or index2
by 1 where the element is put to nums1[index]
.
When only one array has remaining elements, put the elements from the array to the remaining positions in nums1[index]
.
2 pitfalls
- 1) Don’t use nums1.length if you give m, because nums1 is followed by a row of 0
- 2) Note that the pointer of p1 or p2 will be reduced to a negative number, then index error, so add a check
Code
-
import java.util.Arrays; public class Merge_Sorted_Array { public static void main(String[] args) { Merge_Sorted_Array out = new Merge_Sorted_Array(); Solution s = out.new Solution(); int[] nums1 = new int[]{1}; s.merge(new int[]{}, 0, nums1, 1); System.out.println(Arrays.toString(nums1)); } class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return; } int p1 = m - 1; int p2 = n - 1; for (int i = m + n - 1; i>= 0; i--) { int v1 = nums1[p1]; int v2 = p2 >= 0 ? nums2[p2] : Integer.MIN_VALUE; if (v1 > v2) { nums1[i] = nums1[p1--]; } else { nums1[i] = nums2[p2--]; } } } } } ############ class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while (j >= 0) { if (i >= 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } } }
-
// OJ: https://leetcode.com/problems/merge-sorted-array/ // Time: O(M + N) // Space: O(1) class Solution { public: void merge(vector<int>& A, int m, vector<int>& B, int n) { for (int i = m - 1, j = n - 1, k = m + n - 1; k >= 0; --k) { if (j < 0 || (i >= 0 && A[i] > B[j])) A[k] = A[i--]; else A[k] = B[j--]; } } };
-
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ i, j, k = m - 1, n - 1, m + n - 1 while j >= 0: # what if j=-1 already but k is not 0 yet? e.g. m=[1,2,0], n=[3] ==> then no more ops needed, rest of m[] already sorted, so this while is good enough if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1 ############ class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: void Do not return anything, modify nums1 in-place instead. """ end = m + n - 1 m -= 1 n -= 1 while end >= 0 and m >= 0 and n >= 0: if nums1[m] > nums2[n]: nums1[end] = nums1[m] m -= 1 else: nums1[end] = nums2[n] n -= 1 end -= 1 while n >= 0: nums1[end] = nums2[n] end -= 1 n -= 1 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ p = m + n - 1 m -= 1 n -= 1 while m >= 0 and n >= 0: if nums1[m] < nums2[n]: nums1[p] = nums2[n] p -= 1 n -= 1 else: nums1[p] = nums1[m] p -= 1 m -= 1 if m != 0: while m >= 0: nums1[p] = nums1[m] p -= 1 m -= 1 if n != 0: while n >= 0: nums1[p] = nums2[n] p -= 1 n -= 1
-
func merge(nums1 []int, m int, nums2 []int, n int) { i, j, k := m - 1, n - 1, m + n - 1 for j >= 0 { if i >= 0 && nums1[i] > nums2[j] { nums1[k] = nums1[i] i-- } else { nums1[k] = nums2[j] j-- } k-- } }
-
/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function (nums1, m, nums2, n) { let i = m - 1, j = n - 1, k = m + n - 1; while (j >= 0) { if (i >= 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } };
-
class Solution { /** * @param Integer[] $nums1 * @param Integer $m * @param Integer[] $nums2 * @param Integer $n * @return NULL */ function merge(&$nums1, $m, $nums2, $n) { while (count($nums1) > $m) { array_pop($nums1); } for ($i = 0; $i < $n; $i++) { array_push($nums1, $nums2[$i]); } asort($nums1); } }
-
impl Solution { pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) { let (mut m, mut n) = (m as usize, n as usize); for i in (0..m + n).rev() { nums1[i] = match (m == 0, n == 0) { (true, false) => { n -= 1; nums2[n] } (false, true) => { m -= 1; nums1[m] } (_, _) => { if nums1[m - 1] > nums2[n - 1] { m -= 1; nums1[m] } else { n -= 1; nums2[n] } } } } } }
-
/** Do not return anything, modify nums1 in-place instead. */ function merge(nums1: number[], m: number, nums2: number[], n: number): void { for (let i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) { nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; } }