【スナップノート75】色分類

タイトル

赤、白、青の合計n要素を含む配列が与えられ、同じ色の要素が隣接し、赤、白、青の順に並べ替えられる.
この問題では、整数0、1、2を使用して、赤、白、青をそれぞれ表します.
例1:

 ：nums = [2,0,2,1,1,0]
 ：[0,0,1,1,2,2]

例2:

 ：nums = [2,0,1]
 ：[0,1,2]

例3:

 ：nums = [0]
 ：[0]

例4:

 ：nums = [1]
 ：[1]

ヒント:

n == nums.length

1 <= n <= 300

nums[i]は0、1または2

である.
ステップ:

コードライブラリのソート関数を使用しないでこの問題を解決できますか?

定数空間のみを使用したスキャンアルゴリズムを考え出せますか?

解法1(正しい)

アイデア:
golang独自のメソッドを直接利用してソートします.最終的な配列は0,1,2の順序で配列されるので、実際にはどのソートアルゴリズムでも問題を解決することができます.
コード:

func sortColors(nums []int) {
     
   sort.Ints(nums)
}

結果:
実行結果:実行時間:0 msにより、すべてのGoコミットで100.00%のユーザメモリ消費量:2 MBを破り、すべてのGoコミットで14.30%のユーザを破った

解法2

アイデア:
配列を巡回し、0を左側に、2を右側に配置します.一度巡回すれば完了するので、時間の複雑さはO(n)です.
コード:

func sortColors(nums []int) {
     
   left, right := 0, len(nums)-1
   for left < len(nums) && nums[left] == 0 {
     
      left++
   }
   for right >= 0 && nums[right] == 2 {
     
      right--
   }
   for i := left; i <= right && left <= right; {
     
      if left > i {
     
         i = left
      }
      switch nums[i] {
     
      case 0:
         nums[left], nums[i] = nums[i], nums[left]
         left++
      case 2:
         nums[right], nums[i] = nums[i], nums[right]
         right--
      default:
         i++
      }
   }
}

結果:
実行結果:
実行時間:0 ms、すべてのGoコミットで100.00%のユーザーを破った
メモリ消費量:2 MB、すべてのGoコミットで62.50%のユーザーを破った
公式の答え:
答えの3番目の解法と同じです.
https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/