面试经典150题 P88 合并两个有序数组

---

时间轴

时间轴

2025-09-27

init

双指针

---

题目：

P88 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

这题其实可以原地合并，因为 num1 后 n 个元素为 0，可以从后往前合并。但下面的代码未考虑到这点。注意 std::move，它其实是将参数 t 转换为一个右值引用类型，不会拷贝内存，不会释放资源，不会调用构造函数和析构函数

template <typename T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept {
    return static_cast<typename std::remove_reference<T>::type&&>(t);
}

以 std::vector 为例：

std::vector<int> a = {1, 2, 3};
std::vector<int> b = std::move(a);

这里：std::move(a) 把 a 变成右值引用。编译器会选择 vector 的移动构造函数，而不是拷贝构造。移动构造函数做的事：

• 把 a 的内部指针直接“偷走”，交给 b。
• 把 a 的指针设为空，避免析构时释放同一块内存。

所以最后：b 持有 {1,2,3} 的数据。a 变成空的（size()==0，但仍然是合法对象）

总结：
nums1 = std::move(vec);

• 旧内容自动释放（移动赋值内部完成）
• 新内容接管
• vec 变空不需要自己手动调用析构函数。

#include <vector>
using std::vector;

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