2. merge two ordered arrays

Title Description

Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .
Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .
Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .

Their thinking

Solution 1 ： Double finger needling
Ideas ：
Time complexity ：O(n)
Spatial complexity ：O(m+n)=O(n)
Solution 2 ： Direct merge sequence method
Ideas ： Merge the two arrays directly , Then sort the merged array
Time complexity ： On average O((m+n)log(m+n))
Spatial complexity ： On average O(log(m+n))
Solution 3 ： Reverse double pointer method
Ideas ： Traverse and compare the two arrays from back to front , And then embed the larger nums1 Behind
Time complexity ：O(m+n)
Spatial complexity ：O(l)

Code

Solution 1 ： Double finger needling （ Write point redundancy ）

   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<m && j<n){
    
                     if((nums1[i]<=nums2[j])){
    
                         arr[r]=nums1[i];
                         r++;
                         i++;
                     }else{
    
                         arr[r]=nums2[j];
                         r++;
                         j++;
                     }
                 }
             if(i<m){
    
                 for(;i<m;i++)
                     arr[r++]=nums1[i];
             }
             if(j<n){
    
                for (;j<n;j++)
                    arr[r++]=nums2[j];
             }
             for(int x=0;x<m+n;x++){
    
                 nums1[x]=arr[x];
             }
         }else if (m==0 && n!=0){
    
             for (int c=0;c<n;c++)
                 nums1[c]=nums2[c];
         }else{
    
         }
    }

Solution 2 ： Direct merge sequence method

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
    

        for(int i=0;i<n;i++)
            nums1[m+i]=nums2[i];
        Arrays.sort(nums1);
    }

Solution 3 ： Reverse double pointer method

    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;
       }

   }   

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/merge-sorted-array