LeetCode //88. Merge Sorted Array-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //88. Merge Sorted Array。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

88. Merge Sorted Array

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:

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:

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:

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$

From: LeetCode
Link: 88. Merge Sorted Array
文章来源地址https://www.toymoban.com/news/detail-521283.html

Solution:

Ideas：

The idea here is to use two pointers approach where we start filling nums1 from the end. We take two pointers, one at the end of the meaningful part of nums1 (at index m-1), and another at the end of nums2 (at index n-1). We then compare the elements at these pointers in nums1 and nums2, and fill the larger one at the end of nums1 (at index m+n-1). We then decrement the corresponding pointer and the filling position. We repeat this process until all the elements of nums2 are traversed.

Code:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    // Get last index of array nums1 and nums2
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;

    // Merge nums1 and nums2 starting from last element in each
    while (j >= 0) {
        // if all elements of nums1 are processed, copy remaining nums2 elements and break
        if (i < 0) {
            nums1[k--] = nums2[j--];
            continue;
        }
        // if current element of nums1 is greater than current element of nums2, 
        // put this element at the end of nums1 and decrement i.
        // otherwise, do same with nums2
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
}