合并两个有序数列【leetcode】 --java实现

痛定思痛。 2022-03-10 09:42 195阅读 0赞

### 题目描述： ###

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

**说明:**

*  初始化 *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]

### 分析： ###

两个数组都是有序的，并且数组1的空间足够，所以根据题意不需要再开辟新的空间

### 思路: ###

比较两个数组最大的数，将比较大的一个放在m+n-1的位置上，再用其中较小的一个与另一个数组倒数第二位比较，大的插入m+n-2的位置上，依次类推：

第一次比较：nums=\{1,2,3,0,0,6\} (3与6比较大的插入最后)

第二次比较：nums=\{1,2,3,0,5,6\} (3与5比较大的插入倒数第二位)

特殊情况：当第一个数组为空时，直接把第二个数组的元素按顺序插入第一个数组，当第二个数组为空时输出第一个数组

### 代码： ###

class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i = m - 1;
            int j = n - 1;
            int index = m + n - 1;
            while(j >= 0){
                if(i < 0){
                    nums1[index--] = nums2[j--];
                } 
                else if(nums1[i] <= nums2[j]){
                    nums1[index--] = nums2[j--];
                }   
                else if(nums1[i] > nums2[j]){
                    nums1[index--] = nums1[i--];
                }
            }
        }
    }