Merge Sorted Array Problem


Description

LeetCode Problem 88.

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

1
2
3
4
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

1
2
3
4
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

1
2
3
4
5
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m + n - 1, j = m - 1;
        int k = 0;
        while (j >= 0) {
            nums1[i] = nums1[j];
            i --;
            j --;
        }
        i ++, j ++;
        while ((j < n) && (i < m + n)) {
            if (nums2[j] < nums1[i]) {
                nums1[k] = nums2[j];
                j ++;
            } else {
                nums1[k] = nums1[i];
                i ++;
            }
            k ++;
        }
        while (j < n) {
            nums1[k] = nums2[j];
            j ++, k ++;
        }
        while (i < m + n) {
            nums1[k] = nums1[i];
            i ++, k ++;
        }
        return;
    }
};




Related Posts

Reverse Words In A String Problem

LeetCode 151. Given an input string s, reverse the order...

Compare Version Numbers Problem

LeetCode 165. Given two version numbers,version1 and version2, compare them....

Valid Palindrome Problem

LeetCode 125. A phrase is a palindrome if, after converting...

Remove Duplicates from Sorted List II Problem

LeetCode 82. Given the head of a sorted linked list,...

Remove Duplicates from Sorted Array II Problem

LeetCode 80. Given an integer array nums sorted in non-decreasing...

Partition List Problem

LeetCode 86. Given the head of a linked list and...