题目链接

88. 合并两个有序数组 - 力扣（LeetCode）

题目描述

合并两个非递减排序的整数数组，不允许另外开辟空间，排序后的数据放到第一个数组中，第一个数组的长度为两个数组数据的长度之和。

输入输出样例

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

题目解释

双指针，从每个数组的下标为数据长度的位置开始，

把两个指针指向的数据中更大的数字放到第一个数组的结尾

代码

个人实现

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
33
34
35
36

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1;
        int end = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[end--] = nums1[i--];
            } else {
                nums1[end--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[end--] = nums2[j--];
        }
    }
};


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1;
        int end = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[end--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }

        while (n >= 0) {
            nums1[end--] = nums2[n--];
        }
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-sorted-array/solutions/666608/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};