LeetCode力ボタン75.色の分類

タイトル説明(中難易度)
配列を与えて、含まれる数は0,1,2の1つだけで、これらの数字を小さいものから大きいものに並べ替えます.
解法一
タイトルの下のFollow upは1つの解法に言及して、1回の配列を遍歴して、0の出現の回数を統計して、1の出現の回数、2の出現の回数、それから更に配列を遍歴して、回数によって、配列の要素を相応の値に変えます.もちろん私たちは0の回数と1の回数を記録するだけで、残りは2の回数です.

public void sortColors(int[] nums) {
    int zero_count = 0;
    int one_count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            zero_count++;
        }
        if (nums[i] == 1) {
            one_count++;
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (zero_count > 0) {
            nums[i] = 0;
            zero_count--;
        } else if (one_count > 0) {
            nums[i] = 1;
            one_count--;
        } else {
            nums[i] = 2;
        }
    }
}

時間複雑度:O(n).
空間複雑度:O(1).
解法二
上のアルゴリズムでは,配列を2回遍歴し,1回だけ遍歴する方法を考えてみよう.単純な場合、0と1の2つの数しか含まれていないとしたら、どうすればいいのでしょうか.
元の配列が1 0 1 0だと仮定すると、ポインタを1つ使うことができます.zero_positionは、そのポインタが指す位置を意味し、前の位置はすべて0である.それからもう一つのポインタiでこの配列を巡り、0を見つけたら0を現在のzero_に置きます.positionが指す位置、zero_移動後.Zでzero_を表すposition、下の遍歴過程を見てください.

1 0 1 1 0       Z,i     0    ，i   
^
Z
i

1 0 1 1 0      0，  Z       0，    Z           ，Z     
^ ^
Z i

0 1 1 1 0   i     
  ^
  i
  Z
  
0 1 1 1 0  i     
  ^ ^
  Z i

0 1 1 1 0  i     
  ^   ^
  Z   i
  
0 1 1 1 0     0，  Z       0，    Z           ，Z     
  ^     ^
  Z     i
  
0 0 1 1 1      
    ^   ^
    Z   i

私たちの現在の問題に戻って、私たちは3つの数字を持っています.それでは、2つのポインタを使うことができます.1つはzeroです.positionは、前と同じように、前の位置をすべて0にします.もう一つのポインタ、two_position、ここに注意して、その後ろの位置はすべて2を保存します.そして配列全体を巡るだけでいいです.
下辺は1つの遍歴の過程の中の図を描いて、理解して、Zの前はすべて0を保存して、Tの後ろはすべて2を保存します.

0 1 0 2 1 2 2 2
  ^ ^   ^
  Z i   T

public void sortColors(int[] nums) {
    int zero_position = 0;
    int two_position = nums.length - 1;
    for (int i = 0; i <= two_position; i++) {
        if (nums[i] == 0) {
            //          
            int temp = nums[zero_position];
            //  0    
            nums[zero_position] = 0;
            //        
            nums[i] = temp;
            //      
            zero_position++;
        } else if (nums[i] == 2) {
            //          
            int temp = nums[two_position];
            //  2    
            nums[two_position] = 2;
            //        
            nums[i] = temp;
            //      
            two_position--;
            //       ，               i    ，
            //               ，    for       i++         
            //    i--
            //      zero_position         ，             
            //          
            i--;
        }
    }
}

時間複雑度:O(n).
空間複雑度:O(1).
解法三
解法2には全部で3つの数があり、自然に3つの部分に分けられ、2つのポインタで間隔を置くことができますが、5つの数があれば、解法2は適用されないかもしれません.leetcodeで別の解法を発見し,ここの解法2を参考に,大問題化小の思想を用いた.
3つのポインタn 0,n 1,n 2を用いて,配列された配列の現在の0の末尾,1の末尾,2の末尾をそれぞれ表す.

0  0  1  2  2  2  0  2  1
   ^  ^        ^  ^
  n0 n1       n2  i

次に、現在iの位置を0に遍歴し、n 2ポインタを後ろに移動し、現在の数字を2に設定し、n 1ポインタを後ろに移動し、現在の数字を1に設定し、n 0ポインタを後ろに移動し、現在の数字を0に設定するだけです.

0  0  1  2  2  2  2  2  1  n2        
   ^  ^           ^  
   n0 n1          i
                  n2  
                  
0  0  1  1  2  2  2  2  1  n1       
   ^     ^        ^  
   n0    n1       i
                  n2                   

0  0  0  1  2  2  2  2  1  n0       
      ^  ^        ^  
      n0 n1       i
                  n2                    

次に、iが指す0を現在の順序の0に挿入する位置の末尾に達する.
そのため、前に新しい数字が挿入されているため、必ず数字が上書きされます.ポインタを後ろに移動した後、対応するポインタの位置を対応する数にします.n 2ポインタを後ろに移動して2にします.n 1ポインタを後ろに移動して1にします.例えば、前に3つの2があった場合、前に1つの数字が挿入されているため、1つの2が上書きされるので、1つの2を追加します.

public void sortColors(int[] nums) {
    int n0 = -1, n1 = -1, n2 = -1;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
            n2++;
            nums[n2] = 2;
            n1++;
            nums[n1] = 1;
            n0++;
            nums[n0] = 0;
        } else if (nums[i] == 1) {
            n2++;
            nums[n2] = 2;
            n1++;
            nums[n1] = 1;
        } else if (nums[i] == 2) {
            n2++;
            nums[n2] = 2;
        }
    }
}

時間複雑度:O(n).
空間複雑度:O(1).
総
解法二ポインタを利用して、元の空間に物を保存するのは古典的です.解法三、実は本質は私たちがよく使う再帰思想で、まず小さな問題が解決したと仮定して、それからもう一つの数がどう操作すればいいかを仮定します.
もっと詳しくて分かりやすい問題の詳細は
leetcode.wang .