LeetCode_Day17

[88] 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/description/

• algorithms
• Easy (49.33%)
• Likes: 808
• Dislikes: -
• Total Accepted: 291.8K
• Total Submissions: 589.2K
• Testcase Example: ‘[1,2,3,0,0,0]\n3\n[2,5,6]\n3’
• Source Code: 88.merge-sorted-array.cpp

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

 

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[i] <= 109

方法1: 优美的双指针!

由于两个数组是有序的, 所以可以分别在两个数组末尾设置指针, 比较他们的值, 较大的直接写入 nums1 数组的末尾, 为了写入, 还需设置一个 pos 指针来记录位置

当 nums1 完成重写, 那么可直接将 nums2 中的数写入 nums1 即可; 若 nums2 先完成, 因为 nums1 中本就有序, 则完成重排

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

复杂度分析:

• 时间复杂度: O(m+n) , 最多移动 m+n 次
• 空间复杂度: O(1) , 直接在 nums1 上操作, 无需额外空间

注意: 这里用到了 a++, ++a 的一些小技巧.

• a++ , 将a加1, 返回值为 a
• ++a , 将a加1, 返回值为 a+1
• 若只希望增加a的值, 不需要返回值, 则推荐 ++a , 运行速度快