LeetCode_排序_简单_88.合并两个有序数组

蔚落 2023-10-06 18:44 32阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你两个有序整数数组 nums1 和 nums2，请你**将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组**。  
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

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

**示例 2：**  
输入：nums1 = \[1\], m = 1, nums2 = \[\], n = 0  
输出：\[1\]

**提示：**  
nums1.length == m + n  
nums2.length == n  
0 <= m, n <= 200  
1 <= m + n <= 200  
\-109 <= nums1\[i\], nums2\[i\] <= 109

**进阶**：你可以设计实现一个时间复杂度为 O(m + n)、空间复杂度为 O(1) 的算法解决此问题吗？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-sorted-array

## 2.思路 ##

（1）归并算法  
本题比较容易想到的算法是归并排序中的一次归并算法，其具体步骤如下：

*  先创建一个长度为 m + n 的临时一维数组 tmpArr；
 *  每次从 nums1 和 nums2 中取出一个元素进行比较，将较小者放入 tmpArr，最后将各段中余下的部分直接复制到 tmpArr 中；
 *  这样 tmpArr 就是一个有序表，最后再将其复制到 nums1 中即可。

（2）合并后排序  
本思路较为简单粗暴，先将数组 nums2 添加到数组 nums1 的尾部，然后直接对 nums1 进行排序即可。

（3）原地归并  
本方法的时间复杂度为 O(m + n)、空间复杂度为 O(1)。

## 3.代码实现（Java） ##

//思路1————归并算法
    class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int[] tmpArr = new int[m + n];
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < m && j < n) {
        
                if (nums1[i] <= nums2[j]) {
        
                    tmpArr[k++] = nums1[i++];
                } else {
        
                    tmpArr[k++] = nums2[j++];
                }
            }
            if (i < m) {
        
                //将数组 nums1 中剩余的部分赋值到 tmpArr 中
                System.arraycopy(nums1, i, tmpArr, k, m - i);
            }
            if (j < n) {
        
                //将数组 nums2 中剩余的部分赋值到 tmpArr 中
                System.arraycopy(nums2, j, tmpArr, k, n - j);
            }
            //将 tmpArr 中的元素复制到 nums1[0...m + n - 1] 中
            System.arraycopy(tmpArr, 0, nums1, 0, m + n);
        }
    }

//思路2————合并后排序
    class Solution {
        
    	public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    		//将数组 nums2 添加到数组 nums1 的尾部
    	    for (int i = 0; i < n; ++i) {
        
    	        nums1[m + i] = nums2[i];
    	    }
    	    //直接对 nums1 进行排序
    	    Arrays.sort(nums1);
    	}
    }

//思路1————原地归并
    class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int p1 = m - 1;
            int p2 = n - 1;
            int p = m + n - 1;
            while (p1 >= 0 && p2 >= 0) {
        
                if (nums1[p1] > nums2[p2]) {
        
                    nums1[p] = nums1[p1];
                    p1--;
                } else {
        
                    nums1[p] = nums2[p2];
                    p2--;
                }
                p--;
            }
            //将剩余的 nums2 元素复制到 nums1 中
            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        }
    }