88.合并两个有序数组

一、题述

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

初始化 nums1nums2 的元素数量分别为 mn 。你可以假设 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、直接法

我们可以直接把两个数组拼接起来,然后用sort函数对整合后的数组进行一个排序。

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()); //STL排序
    }
};

复杂度分析

  • 时间复杂度:O((m+n)\log(m+n))O((m+n)log(m+n))。
    快速排序、序列长度为 m+nm+n。
  • 空间复杂度:O(\log(m+n))O(log(m+n))。
    快速排序、序列长度为 m+nm+n。

2、双指针

由于题目中给的两个数组序列是已经排序好的,所以我们可以用双指针的办法,对两数组进行按序组合。

图片来源于:Leetcode官方
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 temp;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                temp = nums2[p2++];
            } else if (p2 == n) {
                temp = nums1[p1++]; //当有一方到头时直接将后半段拼接
            } else if (nums1[p1] < nums2[p2]) {
                temp = nums1[p1++];
            } else {
                temp = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = temp;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i]; //数组赋值
        }
    }
};

复杂度分析

  • 时间复杂度:O(m+n)。
    指针移动单调递增,最多移动 m+n 次,因此时间复杂度为 O(m+n)。
  • 空间复杂度:O(m+n)。
    建立长度为 m+n 的中间数组。

3、逆向双指针(Leetcode解答)

2中,为防止 nums1 中的变量被覆盖,所以我们采用新建一个临时变量的方法以规避这一问题。但同时的,我们也可以采用逆向的方法,可以将指针设置为从后向前遍历,每次取两者之中的较大者放进  nums1​ 的最后面,从后向前覆盖。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = nums1.size();
        while (n > 0) {
            if (m > 0 && nums1[m-1] > nums2[n-1]) {
                nums1[--i] = nums1[--m]; 
            }else{
                nums1[--i] = nums2[--n];  //先自减后操作
            }
        }
    }
};

复杂度分析

  • 时间复杂度:O(m+n)。
    指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)。
  • 空间复杂度:O(1)。
    直接对数组 nums1 原地修改,不需要额外空间。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇