合并兩個(gè)有序數(shù)組

• 第一種方法：直接將兩個(gè)數(shù)組合并柳刮，然后再對(duì)這個(gè)數(shù)組進(jìn)行排序(沒有考慮這個(gè)數(shù)組本來就是有序的)

  • class Answer{
       public static void method1(int nums1[],int m,int nums2[],int n){
             System.arrayCopy(nums2,0,nums1,m,n);//將某個(gè)數(shù)組的第幾個(gè)元素拷貝到目標(biāo)數(shù)組的第一個(gè)元素后面搓谆，拷貝多少個(gè)元素
             Arrays.sort(nums1);//對(duì)合并的數(shù)組進(jìn)行排序
       }
    
    }
    時(shí)間復(fù)雜度是快速排序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);//對(duì)數(shù)組進(jìn)行排序
       }
    
    }
    

• 第二種方法：雙指針/從前往后

  • 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數(shù)組進(jìn)行拷貝与学，然后拿拷貝后的數(shù)組跟nums2數(shù)組進(jìn)行比較，然后將較小的元素插入nums1數(shù)組中
             int p1=0;//指向拷貝的數(shù)組
             int p2=0;//指向nums2數(shù)組的第一個(gè)元素
             int p=0;//指向nums1數(shù)組
             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);
             }
    }
        }
    }
    需要拷貝一個(gè)新的數(shù)組空間
    所以空間復(fù)雜度為O（m）
    而時(shí)間復(fù)雜度是對(duì)數(shù)組一進(jìn)行拷貝和對(duì)數(shù)組而進(jìn)行遍歷所以為O(m+n)
    

• 第三種方法：逆雙指針/從后往前遍歷(不需壓對(duì)數(shù)組一進(jì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;//設(shè)置三個(gè)指針都指向末尾元素
             
             while((p1>=0)&&(p2>=0)){
                nums1[p--]=(nums1[p1]<nums[p2])?nums2[p2--]:nums1[p1--];
                System.arrayCopy(nums2,0,nums1,0,p2+1);//比較兩個(gè)數(shù)組中的元素，將較大的元素放入末尾
             
             }
          
        }
        //時(shí)間復(fù)雜度和第二種方法一樣
        空間復(fù)雜度不需要拷貝一個(gè)數(shù)組所以是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--;
                }
            }
           }
    }