本文共 2636 字，大约阅读时间需要 8 分钟。

title: LeetCode中合并两个有序数组题解

• LeetCode
• 算法
  categories: LeetCode
  abbrlink: ‘34072712’
  date: 2020-12-29 19:45:00

LeetCode中合并两个有序数组题解-java

题目

难度简单723

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

说明：

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

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

提示：

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

题解

方法一：合并后排序

思路

将两个数组进行合并，然后对其进行排序

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        for(int i = 0; i < n; i++){            nums1[m++] = nums2[i];        }        Arrays.sort(nums1);    }}

复杂度分析

• 时间复杂度 : O*((n+m)log(n+m))。
• 空间复杂度 😮*(1)。

提交详情

方法二：双指针从前往后排序

思路

使用P1和P2两个指针，分别为两个数组的头部，在每一步中比较两个指针所在元素的大小，将较小值放在输出数组中，然后，对应指针后移一步，直到两个指针有一方到达尾部，将另一方其余全部元素放在输出数组中

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        // 新建一个数组，复制nums1，作为nums1的副本        int[] nums1Copy = new int[m];        for(int i = 0; i < m; i++){            nums1Copy[i] = nums1[i];        }        // 双指针，分别指向nums1Copy和nums2的头部        int p1 = 0;        int p2 = 0;        // 指向输出数组nums1的头部        int p = 0;        // 当p1 和 p2 双指针均在两个数组之内时        while((p1 < m) && (p2 < n)){            // 输出数组p指针所在的值即为：p1,p2 两个指针所在值的较小值，并将较小值所在指针++，然后p指针向后移一位            nums1[p++] = (nums1Copy[p1] < nums2[p2]) ? nums1Copy[p1++] : nums2[p2++];        }        // 如果p1指针未到尾部，将剩余部分全部复制到输出数组中        if(p1 < m){            for(int j = p1; j < m; j++){                nums1[p++] = nums1Copy[j];            }        }        // 若P2指针未到尾部，将剩余部分复制到输出数组中        if(p2 < n){            for(int i = p2; i < n; i++){                nums1[p++] = nums2[i];            }        }    }}

复杂度分析

• 时间复杂度 : O*(n+*m)。
• 空间复杂度 : O*(m)。

提交详情

方法三：双指针，从后往前

思路

使用P1和P2两个指针，分别为两个数组的尾部，在每一步中比较两个指针所在元素的大小，将较大值放在输出数组中，然后，对应指针前移一步，直到两个指针有一方到达头部，将另一方其余全部元素放在输出数组中

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        // 新建两个指针p1,p2, 分别指向两个数组的尾部        int p1 = m -1;        int p2 = n -1;        // 新建一个指针p,指向nums1 的尾部        int p = m + n - 1;        // 当p1，p2指针均未到达头部时，        while((p1 >= 0) && (p2 >= 0)){            // 此时数组元素为两个指针指向的元素的较大值，之后，对应指针--，总指针p--            nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];        }        // 如果p1 < 0 ，此时数组2还未到达头部，此时将p2 指针到头部中的元素全部复制给数组        for(int i = p2; i >= 0; i--){            nums1[p--] = nums2[i];        }        // 如果p2 < 0 ，说明数组p1未到达头部，但此时nums1以有原来元素，故不需要复制    }}

复杂度分析

• 时间复杂度 : O(n + m)O(n+m)。
• 空间复杂度 : O(1)O(1)。

提交详情

转载地址：http://jkwzi.baihongyu.com/