合并两个有序数组

合并两个有序数组

• 第一种方法：直接将两个数组合并，然后再对这个数组进行排序(没有考虑这个数组本来就是有序的)

  • class Answer{
       public static void method1(int nums1[],int m,int nums2[],int n){
             System.arrayCopy(nums2,0,nums1,m,n);//将某个数组的第几个元素拷贝到目标数组的第一个元素后面，拷贝多少个元素
             Arrays.sort(nums1);//对合并的数组进行排序
       }
    
    }
    时间复杂度是快速排序O(log(m+n))
    

  • class Answer{
       public static void method1(int nums1[],int m,int nums2[],int n){
            for(int i=0;i!=n;++i){
                nums1[+i]=nums2[i];
            }
             Arrays.sort(nums1);//对数组进行排序
       }
    
    }
    

• 第二种方法：双指针/从前往后

  • class Answer{
        public static void method1(int nums1[],int m,int nums2[],int n){
             int [] nums1_copy=new int[m];
             System.arrayCopy(nums1,0,nums1_copy,0,m);//将nuns1数组进行拷贝，然后拿拷贝后的数组跟nums2数组进行比较，然后将较小的元素插入nums1数组中
             int p1=0;//指向拷贝的数组
             int p2=0;//指向nums2数组的第一个元素
             int p=0;//指向nums1数组
             while((p1<m)&&(p2<n)){
             nums1[p++]=(nums1_copy[p1]<nums2[p2])?nums1_copy[p1++]:nums2[p2++];
             
             if(p1<m){
               System.arrayCopy(nums1_copy,p1,nums1,p1+p2,m+n-p1-p2);
             }
             if(p2<n){
               System.arrayCopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);
             }
    }
        }
    }
    需要拷贝一个新的数组空间
    所以空间复杂度为O（m）
    而时间复杂度是对数组一进行拷贝和对数组而进行遍历所以为O(m+n)
    

• 第三种方法：逆双指针/从后往前遍历(不需压对数组一进行拷贝)

  • class Answer{
        public static void method1(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)){
                nums1[p--]=(nums1[p1]<nums[p2])?nums2[p2--]:nums1[p1--];
                System.arrayCopy(nums2,0,nums1,0,p2+1);//比较两个数组中的元素，将较大的元素放入末尾
             
             }
          
        }
        //时间复杂度和第二种方法一样
        空间复杂度不需要拷贝一个数组所以是O(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(p>=0&&p1>=0&&p2>=0){
                if(nums1[p1]<nums2[p2]){
                    nums1[p]=nums2[p2];
                    p2--;
                }else{
                    nums1[p]=nums1[p1];
                    p1--;
                }
                p--;
            }
            if(p1<0){
                while(p>=0&&p2>=0){
                    nums1[p]=nums2[p2];
                    p--;
                    p2--;
                }
            }
           }
    }