合并两个有序数组

绝地灬酷狼 2022-12-08 05:15 196阅读 0赞

# 合并两个有序数组 #

## 1、参考资料 ##

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

## 2、题目要求 ##

> **题目描述**

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

> **说明:**

1.  初始化 *nums1* 和 *nums2* 的元素数量分别为 *m* 和 *n* 。
2.  你可以假设 *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]

## 3、代码思路 ##

双指针

1.  分别为两个数组 `nums1[]` 和 `nums2[]` 分配一个指针：`nums1Pointer` 和 `nums2Pointer`，我们遍历数组，比较 `nums1[nums1Pointer]` 和 `nums2[nums2Pointer]` 的大小，将其按序排放在 `nums1[]` 数组中
2.  我们如果按照从前往后的顺序进行遍历，那么 `nums1[]` 数组后面的额外空间就利用不上(或者插入一个数就需要整体移动，这样更不划算)，所以从前往后的遍历 + 双指针需要开辟额外的数组空间
3.  我们如果按照从后往前的顺序进行遍历，那么 `nums1Pointer` 初始化时指向 `nums1[]` 数组最后一个有效元素，`nums2Pointer` 初始化时指向 `nums2[]` 数组最后一个有效元素，我们将 `nums1[nums1Pointer]` 和 `nums2[nums2Pointer]` 中较大的元素依次排在数组的后面，这是又需要一个指针 `insertIndex`：用于记录当前插入元素的位置

## 4、代码实现 ##

代码

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int nums1Pointer = m - 1; // nums1[] 数组的指针
            int nums2Pointer = n - 1; // nums2[] 数组的指针
            int insertPointer = nums1.length - 1; // 插入位置的指针
    
            // 当 insertPointer < 0 时，证明数组合并完成
            while (insertPointer >= 0) {
        
                if (nums1Pointer < 0 || nums2Pointer < 0) {
        
                    // 如果其中有一个数组已经复制完了，即其中有一个数组的指针已经小于 0 了
                    nums1[insertPointer--] = (nums1Pointer > nums2Pointer) ? nums1[nums1Pointer--] : nums2[nums2Pointer--];
                } else {
        
                    // 否则根据 nums1[nums1Pointer] 和 nums2[nums2Pointer] 的大小进行插入
                    nums1[insertPointer--] = (nums1[nums1Pointer] > nums2[nums2Pointer]) ? nums1[nums1Pointer--] : nums2[nums2Pointer--];
                }
            }
        }
    }