【leetcode】88. 合并两个有序数组

题目内容

88. 合并两个有序数组

思路分析

参考资料

方法一：插入排序

看到本题，自己想的解法是进行插入排序。

与正常的插入排序一样，都是二分查找+插入的思路。只不过本题有一点点不同：数组一中用0预留出了数组二的位置，因此

数组一整体相当于不是有序的，如[1, 2, 3, 0, 0, 0]。不可以直接在begin()到end()的范围内使用lower_bound()函数。
数组的空间是有限的，因此不能直接使用insert()函数，否则会扩大数组一的空间，数组一中的0也无法处理。

为解决上面两个问题

使用一个全局变量nums1_size来存储nums1中有意义数字（非占位符数字）的个数，则lower_bound的范围为begin()到begin() + nums1_size。
自己编写插入函数，思路为：将插入位置position到nums1_size-1下标处的所有数字都往后挪一格，再将要插入的数放置于position处

方法二：合并后排序

可以将数组二直接加到数组一里，然后执行排序算法即可。

方法三：双指针

由于两个数组都是有序的，因此可以新开辟一个大小为m+n的数组result。然后对比两个要排序的数组的第一个元素，谁小就将谁加入到result数组的末尾；另外当一个数组的元素全部插入完毕后，后续直接插入另一个数组的剩余元素。

方法四：逆向双指针

方法三中新开辟了一个大小为m+n的数组，比较蠢。

观察可知，nums1的后面有一部分是空的，因此可以指针从后向前遍历，选取两个数组中较大的值放在nums1的后面，即可在不开辟额外空间的情况下排序。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 插入排序
// 时间复杂度O(n^2)
// 空间复杂度O(1)
class Solution1 {
public:
    int nums1_size; // nums1中有意义的元素个数
    
    void my_insert(vector<int>& nums, int position, int data) {
       // 挪元素：从最后一个有意义的元素处开始倒序直到position处，各往后挪一格
       // 为position处插入元素做准备
       for (auto i = nums1_size - 1; i >= position; --i) {
          nums[i + 1] = nums[i];
       }
       nums[position] = data;
       nums1_size++;
    }

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       nums1_size = m;
       for (int num2 : nums2) {
          auto insert_position = lower_bound(nums1.begin(), 
            nums1.begin() + nums1_size, num2) - nums1.begin();
          my_insert(nums1, insert_position, num2);
       }
    }
};

// 合并后排序
// 时间复杂度O( (m+n)log(m+n) )
// 空间复杂度：平均O( log(m+n) )，最坏O(m+n)
class Solution2 {
public:
    // 快排（写的时候又忘了...）
    void quick_sort(vector<int>& nums) {
       quick_sort(nums, 0, nums.size() - 1);
    }

    void quick_sort(vector<int>& nums, int left, int right) {
       if (left >= right) return;

       int pivot = nums[left];
       int i{ left }, j{ right };

       // 外层while控制i与j是否相遇
       while (i != j) {
          // 右指针需要寻找<=pivot的数
          while (i < j && nums[j] > pivot) {
             --j;
          }

          // 左指针需要寻找>pivot的数
          while (i < j && nums[i] <= pivot) {
             ++i;
          }

          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
       }

       nums[left] = nums[i];
       nums[i] = pivot;
      
       quick_sort(nums, left, i - 1);
       quick_sort(nums, i + 1, right);
    }

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       // 合并数组
       for (int i = m; i < m + n; ++i) {
          nums1[i] = nums2[i - m];
       }

       // 排序
       quick_sort(nums1);
    }
};

// 双指针
// 时间复杂度O(m+n)
// 空间复杂度O(m+n)
class Solution3 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       vector<int> result;
       int cur, p1{ -1 }, p2{ -1 };
       while(p1 < m - 1 || p2 < n - 1) {
          if (p1 == m - 1) {
             cur = nums2[++p2];
          } else if (p2 == n - 1) {
             cur = nums1[++p1];
          } else if (nums1[p1 + 1] <= nums2[p2 + 1]) {
             cur = nums1[++p1];
          } else {
             cur = nums2[++p2];
          }
          result.push_back(cur);
       }
       copy(result.begin(), result.end(), nums1.begin());
    }
};

// 逆向双指针
// 时间复杂度O(m+n)
// 空间复杂度O(1)
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       int cur, p1{m}, p2{n}, insert_position{m + n - 1};
       while(p1 != 0 || p2 != 0) {
          if (p1 == 0) {
             cur = nums2[--p2];
          } else if (p2 == 0) {
             cur = nums1[--p1];
          } else if (nums1[p1 - 1] >= nums2[p2 - 1]) {
             cur = nums1[--p1];
          } else {
             cur = nums2[--p2];
          }

          nums1[insert_position] = cur;
          insert_position--;
       }  
    }
};

int main() {
   Solution s;
   vector<int> nums1{1,2,3,0,0,0}, nums2{2,5,6};
   int m{3}, n{3};
   s.merge(nums1, m, nums2, n);
   int a = 0;
}

收获

插入排序这种还是得多练，之前写了两遍又忘了
一题多解还是很有必要的