Description

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

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Answer & Explaining

#include <stdio.h>

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 初始化三個指標
    int p1 = m - 1;  // 指向 nums1 尾端
    int p2 = n - 1;  // 指向 nums2 尾端
    int p = m + n - 1;  // 指向合併後陣列的尾端

    // 從後往前進行合併
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) { //陣列一p1 index >陣列二p2 index
            nums1[p] = nums1[p1];//值放入
            p1--; //p1向前移
        } else {
            nums1[p] = nums2[p2];
            p2--; //p2向前移
        }
        p--; //p指標向前移
    }

    // 若 nums2 還有剩餘元素，將它們複製到 nums1
    while (p2 >= 0) {
        nums1[p] = nums2[p2]; //直接把剩下的num2元素放到num1
        p2--;
        p--;
    }
}

Testing

#include <stdio.h>

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 初始化三個指標
    int p1 = m - 1;  // 指向 nums1 尾端
    int p2 = n - 1;  // 指向 nums2 尾端
    int p = m + n - 1;  // 指向合併後陣列的尾端

    // 從後往前進行合併
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) { //陣列一p1 index >陣列二p2 index
            nums1[p] = nums1[p1];//值放入
            p1--; //p1向前移
        } else {
            nums1[p] = nums2[p2];
            p2--; //p2向前移
        }
        p--; //p指標向前移
    }

    // 若 nums2 還有剩餘元素，將它們複製到 nums1
    while (p2 >= 0) {
        nums1[p] = nums2[p2]; //直接把剩下的num2元素放到num1
        p2--;
        p--;
    }
}

int main() {
    // 範例1
    int nums1[] = {1, 2, 3, 0, 0, 0};
    int nums2[] = {2, 5, 6};
    int m = 3, n = 3;
    merge(nums1, 6, m, nums2, 3, n);
    printf("Output: ");
    for (int i = 0; i < m + n; i++) {
        printf("%d ", nums1[i]);
    }
    printf("\n");

    // 範例2
    int nums3[] = {1};
    int nums4[] = {};
    m = 1, n = 0;
    merge(nums3, 1, m, nums4, 0, n);
    printf("Output: ");
    for (int i = 0; i < m + n; i++) {
        printf("%d ", nums3[i]);
    }
    printf("\n");

    // 範例3
    int nums5[] = {0};
    int nums6[] = {1};
    m = 0, n = 1;
    merge(nums5, 1, m, nums6, 1, n);
    printf("Output: ");
    for (int i = 0; i < m + n; i++) {
        printf("%d ", nums5[i]);
    }
    printf("\n");

    return 0;
}