2. 合并两个有序数组

2. 合并两个有序数组

2.合并两个有序数组

题目描述解题思路代码

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解题思路

解法一：双指针法
思路：
时间复杂度：O(n)
空间复杂度：O(m+n)=O(n)
解法二：直接合并后排序法
思路：直接将两个数组合并，然后再对合并后的数组进行排序
时间复杂度：平均情况O((m+n)log(m+n))
空间复杂度：平均情况O(log(m+n))
解法三：逆向双指针法
思路：从后往前对两个数组进行遍历比较，然后将较大的嵌入的nums1的后面
时间复杂度：O(m+n)
空间复杂度：O(l)

代码

解法一：双指针法（写的点冗余）

   public static void merge(int[] nums1, int m, int[] nums2, int n) {
         int[] arr=new int[m+n];
         int i=0;
         int j=0;
         int r=0;
         if(m!=0 && n!=0){
             while(i 
解法二：直接合并后排序法
 
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {

        for(int i=0;i 
解法三：逆向双指针法
 
    public static void merge3(int[] nums1, int m, int[] nums2, int n) {
       int p1 = m - 1, p2 = n - 1;
       int tail = m + n - 1;
       int cur;
       while (p1 >= 0 || p2 >= 0) {
           if (p1 == -1) {
               cur = nums2[p2--];
           } else if (p2 == -1) {
               cur = nums1[p1--];
           } else if (nums1[p1] > nums2[p2]) {
               cur = nums1[p1--];
           } else {
               cur = nums2[p2--];
           }
           nums1[tail--] = cur;
       }

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


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5711878.html