我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

题解

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
class Solution
{
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        int p1 = 0, p2 = 0;
        int sorted[m + n];
        int cur;
        while (p1 < m || p2 < n)
        {
            if (p1 == m) //如果nums1已经全部存入新数组
            {
                cur = nums2[p2++];
            }
            else if (p2 == n) //如果nums2已经全部存入新数组
            {
                cur = nums1[p1++];
            }
            else if (nums1[p1] < nums2[p2])
            {
                cur = nums1[p1++];
            }
            else
            {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i < m + n; i++)
        {
            nums1[i] = sorted[i];
        }
    }
};

思路

双指针，偷一张LeetCode的图:

有序的东西当然可以想到是不是可以用双指针

直接上手：

  1. 新建两个分别指向两个数组头部的指针p1, p2，用于存放排序完成的数组sorted
  2. 比较两个指针当前所指位置的值的大小
  3. 如果某一个数组已经遍历完成，继续返回另一个数组剩下的值即可
  4. 将较小的那个值存入sorted
  5. 由于题目要求返回nums1，复制sorted覆盖num1即可