数组算法题 - 合并两个有序数组

合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode） 刷题时间:

• 25/12/23

我的解法

▼
java
复制代码
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0)
            return;
        for (int i = m, j = 0; i < m + n; i++) {
            nums1[i] = nums2[j];
            j++;
        }

        for (int i = m + n - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums1[j] > nums1[j + 1]) {
                    int temp = nums1[j];
                    nums1[j] = nums1[j + 1];
                    nums1[j + 1] = temp;
                }
            }
        }
    }
}

优点

• 正确处理了n==0的特殊情况
• 先合并再排序的思路
• 使用了经典的冒泡排序法 缺点
• 时间复杂度高
• 没有利用"有序"的条件

题解

1. 方案一（额外空间合并）:
   • 时间复杂度是O($m+n$), 空间复杂度是O($m+n$)
   • 设置额外数组存储结果,采用三指针,最后将结果复制到nums1中

▼
java
复制代码
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        
        // 双指针合并
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        
        // 处理剩余元素
        while (i < m) merged[k++] = nums1[i++];
        while (j < n) merged[k++] = nums2[j++];
        
        // 复制回nums1
        System.arraycopy(merged, 0, nums1, 0, m + n);
    }
}

2. 方案二(原地合并):
   • 时间复杂度是O($m+n$), 空间复杂度是O(1)
   • 与方案一的区别是, 直接在nums1数组上进行操作, 空间复杂度直接降为O(1)

▼
java
复制代码
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return;

        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // 运行到这里, 两者必有一个小于0
        // 如果是j用完了(nums2),那么程序就可以结束了
        // 如果是i先用完了(nums1),那么就把nums2剩余的元素排进去即可
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
    }
}

1. 思路
   • 我的解法使用的是冒泡排序法, 先合并数组, 再使用冒泡排序法进行排序
     • 时间复杂度是O($(m+n)^2$), 空间复杂度是O(1)
     • 可以考虑降低为O($m+n$)
   • 充分利用已知条件: 两个数组都是"有序"的, 可以使用"归并排序"的合并思想
     • 使用三个指针
       • 一个指针i指向nums1的最后有效索引(m-1), 一个指针j指向nums2的最后有效索引(n-1),一个指针k指向nums1的最后索引(m+n-1)
     • 比较nums1[i],nums2[j]的大小,较大者排到nums1的最末尾(nums1[k]).
       • 直到其中一个数组被比较排序完, 这里有一个边界点:
         • 就是如果nums2数组先排序完,那么程序可以直接结束了, 因为nums1数组剩余的元素肯定是有序的,且位置正确.

• 如果nums1数组先排序完, 那么可以直接把nums2数组剩余的元素逐个排进nums1即可

2. 算法思想

• 归并排序(有序数据) - 两个有序数组进行排序, 那么可以使用归并排序的合并思想
  • 时间复杂度的优化
    • 冒泡排序法的O($n^2$)时间复杂度, 必然是要被优化的, 需要优化为$O(n)$.

• 双指针/三指针的应用(合并有序数组/链表) - 指针负责元素的选取, 进行比较 - nums1[i] > nums2[j] -> 取nums1[i], i-- - 否则 -> 取nums2[j], j-- - 每次k--
  • 从后往前操作 - 原地操作
    • 这决定了是采用额外数组存储,还是原地操作
    • 如果需要"原地"修改数组, 且可能会覆盖未处理数据时,就不能使用从前往后.
    • 而是从后往前

3. 题目变式 - 思考

• 如果题目要求改为输出结果为降序呢?
  • 两个升序的数组,输出nums1为降序
• 如果采用原地排序的办法
  • 从前往后: 会直接覆盖未处理的元素(nums1[0]), 不管索引从哪里开始
  • 从后往前: 也可能会覆盖元素, 例如:

• 如果采用额外空间的方法
  • 这道题就很简单了
  • 同样设置两个指针指向两个数组(从0索引开始), 比较大小, 较小者放在额外数组的末尾. 逐个比较存储即可.