ネクタイネットワークアルゴリズム学習ノート-88

ネクタイネットアルゴリズム学習ノート
このシリーズのアルゴリズムのテーマはネクタイネットから来ます
配列クラスアルゴリズム7日目
テーマ:88.2つの配列を結合
2つの整列整数配列*nums 1*とnums 2が与えられ、*nums 2*が*nums 1に結合され、*num 1*が整列配列になるようにします.
例:

  :
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

  : [1,2,2,3,5,6]

説明:

初期化nums 1およびnums 2の要素数は、それぞれmおよびnである.

*nums 1*にはnums 2の要素を保存するのに十分な空間(空間サイズがm+n以上)があると仮定できます.

解題プロセス:
考え方一:
問題を見た最初の考えは、データを挿入してから、データを後ろに移動することですが、データを移動する代価が大きすぎて、その後は配列の長さで十分だと思って、直接後ろから置けばいいです.
コードは次のとおりです.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //      ，                ，            
        
        if((nums1.length == 1) && (nums1[0] == 0)){  //   nums1       
            nums1[0] = nums2[0];
            return;
        }
        
        int keynum = m+n-1; //              
        int arr1 = m-1;
        for(int i = n-1;i>=0;i--){
            for(;arr1>=0;arr1--){
                if(nums2[i] >= nums1[arr1]){
                    nums1[keynum] = nums2[i];
                    keynum--;
                    break;
                }else{
                    nums1[keynum] = nums1[arr1];
                    keynum--;
                }
            }
            if(arr1<0){		//   nums1      nums2   ，       nums2       
                nums1[keynum] = nums2[i];	//         ，        
                keynum--;
            }
        }        
    }
}
// 5ms

次のことを考えます.
実は书き终わって考えて、私はネストの循环を书く必要はないと思って、结局循环の回数は私は知っていて、そこで考えの2がありました.
考え方2:
サイクル数=m+n回、このようなサイクルを直接書けばよい.
コードは次のとおりです.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //      ，                ，            
        
        if((nums1.length == 1) && (nums1[0] == 0)){
            nums1[0] = nums2[0];
            return;
        }
        int k = m+n-1;
        
       for(;k>=0;k--){
            if(m!=0 && n!=0){
                if(nums1[m-1] < nums2[n-1]){
                    nums1[k] = nums2[n-1];
                    n--;
                }else{
                    nums1[k] = nums1[m-1];
                    m--;
                }
            }else if(m==0){
                nums1[k] = nums2[n-1];
                n--;
            }else if(n == 0){
                nums1[k] = nums1[m-1];
                m--;
            }
       }
    }
}
//3ms

次のことを考えます.
これは主にいくつかの特殊な状況に注意しなければなりません.

1.                ，              ，                       ，
2.                              ，                      ；
3.                              ，      。
4.      2、3           ，       。

ネクタイの上のこの問題の他の高品質の例:

class Solution {
  public static void merge(int[] nums1, int m, int[] nums2, int n) {
		//  ：
	   if(n==0) {
		  return;
	   }
		int i = 0,j=0;
		while(i<m) {
			if(nums1[i]<=nums2[j]) {
				i++;
			}else {
				swap(nums1,i++,nums2,j);
				//    
				while(j+1<n&&nums2[j]>nums2[j+1]) {
					swap(nums2, j,(j+1));
					j++;
				}
				j = 0;
			}
		}
		
		while(j<nums2.length) {
			nums1[i++] = nums2[j++];
		}
	}

	private static void swap(int[] nums2, int i, int j) {
		// TODO Auto-generated method stub
		nums2[i] = nums2[i]^nums2[j];
		nums2[j] = nums2[i]^nums2[j];
		nums2[i] = nums2[i]^nums2[j];
	}

	private static void swap(int[] nums1, int i, int[] nums2, int j) {
		int temp = nums1[i];
		nums1[i] = nums2[j];
		nums2[j] = temp;
	}
}
// 4ms

自己整理:
ここでの考え方は,まず最大値を配列2に入れ,次に配列2の値を配列の後ろに置くことである.
この部分はそうは思わなかったが、私がこの問題をするときは数を挿入しようとしただけで、先にソートして挿入しようとは思わなかった.
方法が多く、複数の方位の思考が必要です.