1 题目

88-合并两个有序数组

2 思路

将nums2合入nums1,

双指针：如果从nums1和nums2的头部开始处理，每次比较后将元素放置在nums1的当前位置，nums1的后续元素有一半概率要让出位置，整体向后移动一步，显然时间复杂度为 O(m(m+n))，太过于笨重；

双指针+额外空间：为了避免每次处理都整体向后移动，可以申请一块 m+n 的空间，先放在这里，最后再复制到nums1中，用空间换时间，空间复杂度为 O(m+n)，时间复杂度为 O(m+n)；

双指针+逆向：如果从nums1和nums2的结尾开始处理，每次比较后将元素放置在nums1的最后，这样不会干扰nums1的其他元素，时间复杂度为 O(m+n)，空间复杂度为 O(1)。

3 题解

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

class Solution {
 public:
  // 尾插法
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    // nums1的尾部索引
    int tail = m + n - 1;
    // nums1的原始数据的尾部索引
    --m;
    // nums2的原始数据的尾部索引
    --n;

    while (m >= 0 || n >= 0) {
      if (m == -1) {
        // nums1的原始数据遍历完了，只剩下nums2中还有数据
        nums1[tail--] = nums2[n--];
      } else if (n == -1) {
        // nums2的原始数据遍历完了，只剩下nums1中还有数据
        nums1[tail--] = nums1[m--];
      } else if (nums1[m] > nums2[n]) {
        // nums1[m]的数据大，取nums1[m]
        nums1[tail--] = nums1[m--];
      } else {
        // nums2[n]的数据大，取nums[n]
        nums1[tail--] = nums2[n--];
      }
    }
  }
};

int main() {
  int m, n;
  std::vector<int> nums1, nums2;

  std::string line;
  std::getline(std::cin, line);
  std::istringstream iss1(line);
  int x;
  // nums1
  while (iss1 >> x) {
    nums1.push_back(x);
  }
  m = nums1.size();

  std::getline(std::cin, line);
  std::istringstream iss2(line);
  // nums2
  while (iss2 >> x) {
    nums2.push_back(x);
  }
  n = nums2.size();

  // nums1 后面补0
  nums1.resize(nums1.size() + nums2.size(), 0);

  // 打印原始数据
  std::cout << "Ori:" << std::endl;
  for (int num : nums1) std::cout << num << " ";
  std::cout << std::endl;
  for (int num : nums2) std::cout << num << " ";
  std::cout << std::endl;

  // 处理
  Solution s;
  s.merge(nums1, m, nums2, n);

  // 打印处理后的数据
  std::cout << "Now:" << std::endl;
  for (int num : nums1) std::cout << num << " ";
  std::cout << std::endl;

  return 0;
}

4 其他

在官方题解中，有一个方法是直接合并后排序，即 先将数组 nums2​ 放进数组 nums1​ 的尾部，然后直接对整个数组进行排序。时间复杂度：O((m+n)log(m+n))，空间复杂度：O(log(m+n))。

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());
    }
};

虽然这个方法投机取巧，而且复杂度高，但还是有学习的地方的。

如果nums1和nums2不是 非递减顺序 排列的整数数组，而是乱序数组，那就只能用这个排序方法了。

值得注意的是，代码中使用了 for (int i = 0; i != n; ++i) ，而不是 for (int i = 0; i < n; ++i) 。原本以为 i != n 这种写法可能会有性能上的提升，但是查资料发现并无区别，只是风格不同。而通常更推荐 i < n 这种写法，因为 i != n 这种写法可能会导致死循环（例如在代码逻辑中，可能不小心在某处修改了i，跳过了n，则 i != n 就成了死循环）

下标风格（如数组、vector）：

for (int i = 0; i < n; ++i)

迭代器风格（如list、set、map等）：

for (auto it = container.begin(); it != container.end(); ++it)