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

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

题目

88. 合并两个有序数组

难度简单723

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

说明：

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

示例：

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [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))。
• 空间复杂度 :O*(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)。

提交详情