Sort Colors
各値が 0、1、または 2 である配列 nums が与えられます。これは、赤、白、青のような 3 色を表しています。配列を並べ替えて、すべての 0 が先頭に、次にすべての 1 が続き、最後にすべての 2 が来るようにして、配列を返してください。ライブラリのソート関数を使わずに解いてください。
関数
- numsinteger-array
- 色はそれぞれ0、1、または2
- 戻り値integer-array
- 同じ値を、まずすべての0、次にすべての1、最後にすべての2の順に並べます
制約
1 ≤ nums.length ≤ 1.5 × 104- 各
nums[i]は0、1、または2です。 - 色が欠けている場合があり、配列には色が1つだけ含まれている場合があります。
例
- 入力
- nums = [2, 1, 0, 2, 0, 1, 1]
- 出力
- [0, 0, 1, 1, 1, 2, 2]
- 説明
- 配列には0が2つ、1が3つ、2が2つ含まれているため、結果はまさにそのとおりです。0が2つ、次に1が3つ、その次に2が2つです。
- 入力
- nums = [2, 0, 2]
- 出力
- [0, 2, 2]
- 説明
- 1はまったくありません。1つの0が先頭に移動し、その後に2つの2が続きます。
- 入力
- nums = [1]
- 出力
- [1]
- 説明
- 単一の値はすでに順序どおりなので、配列は変更されずに返されます。
発展問題
配列の長さよりもはるかに小さい k 色が3色の代わりにあったとしたら、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
異なる値は3つしか現れません。一般的なソートではできない、どんなことができますか？
0、1、2の個数を数えて配列を書き換える方法は、2回の走査で機能します。1回の走査では、3つの領域が同時に広がっていく様子をイメージしてください。先頭に0、末尾に2、その間に1が並びます。
3つのインデックスを保持します:
low、mid、high。nums[mid]を読み取ります。0ならlowと交換し、2ならhighと交換し、1ならそのままにします。highとの交換後は、同じ位置をもう一度読み取ります。
解説
0、1、2 だけが現れるので、それらを数えて、2回の走査で配列を書き換えることができます。0の終わりと2の始まりを示す3つのポインターを使えば、1回の走査で、読み取りながら各値を所定の位置に配置できます。この分割手法が、オランダ国旗アルゴリズムです。
手作業でのバブルソート
正しいが、最大のテストでは終わらない
考え方
ライブラリのソートを使わない場合、基準となるのは自分で書くソートです。バブルソートは配列を順に調べ、順序が逆になっている隣り合う要素を入れ替えます。各パスで、そのパス中に見つけた最大値を末尾まで移動させるため、n-1回のパスの後にはすべての位置が確定します。
比較回数は約 n²/2 回です。n = 1.5 × 10^4 の場合は 10^8 を超えますが、そのどれも、値が3種類しかないという事実を利用しません。
アルゴリズム
- 配列に対して n-1 回のパスを実行します。
- 各パスで、まだ確定していない隣り合う要素のすべての組
nums[j]とnums[j + 1]を比較し、左側の要素のほうが大きければ入れ替えます。 - パス番号
done（0 から数えます）の実行後、最後のdone + 1個の位置には確定した値が入るため、次のパスではその手前まで処理します。 numsを返します。
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums色ごとに数えてから、書き直しましょう
考え方
等しい値は互いに置き換えられるため、重要なのは個数だけです。最初の例では、0が2個、1が3個、2が2個あるので、何かを移動する前に答えが決まります。
配列を1回読み取って各値の個数を数え、次に先頭から上書きします。count[0]個の0、count[1]個の1、count[2]個の2です。これが計数ソートです。2回の走査と3つのカウンターで、時間計算量はO(n)、空間計算量はO(1)です。
アルゴリズム
- カウンターを3つ作成し、すべて0にします。
- 各値を読み取り、対応するカウンターに1を加えます。
- 先頭から
count[0]個の0を書き込み、次にcount[1]個の1、最後にcount[2]個の2を書き込みます。 numsを返します。
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return nums3つのポインターを使った1回の走査（オランダ国旗問題）
考え方
読み進めながら、3つの領域を広げます。lowより前はすべて0、lowからmidの直前まではすべて1、highより後ろはすべて2で、nums[mid]からnums[high]までは未読です。
nums[mid]を読みます。1はすでに自分の領域にあるので、midを進めます。0はnums[low]と交換し、両方を進めます。lowから戻ってきた値は1か、まだ1が見つかっていなければ同じ0なので、正しい位置にあります。2はnums[high]と交換し、highを戻します。ただし、highから来た値は未読なので、midはそのままにします。
各ステップでmidが前に進むかhighが後ろに下がるため、ループはnステップ後に終了します。[2, 0, 2]では、最初の2が最後の値と交換され、highは1になります。インデックス0にはまだ2があるので、0と交換します。その0はそのまま残り、結果は[0, 2, 2]になります。
アルゴリズム
low = 0、mid = 0を設定し、highを最後のインデックスに設定します。mid ≤ highの間、nums[mid]を読み取ります。- 値が0なら、
nums[low]と交換し、lowとmidを1つ右に進めます。 - 値が1なら、
midを1つ右に進めます。 - 値が2なら、
nums[high]と交換し、highを1つ左に進めます。midはその位置に留めます。 numsを返します。
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
落とし穴と境界ケース
highとの交換後にmidを進めること。入れ替わってきた値は未読です。[1, 2, 0]では、2が0と入れ替わり、0を読み飛ばすと[1, 0, 2]が返されます。mid < highの間ループすること。2つの位置が一致したとき、その要素はまだ未読です。[1, 0]では、ループは0を読む前に停止し、[1, 0]を返します。- 符号なしインデックスで
highが0未満になること。[2]のような2だけの配列では、highが-1になり、Rustのusizeでアンダーフローします。代わりに、highは未読部分の1つ先に保ちます。
よくある質問3
オランダ国旗問題とは何ですか？
Edsger Dijkstraが提起した問題です。3色のオブジェクト（オランダ国旗の赤、白、青）を、それぞれの色がまとまるように一列に並べます。交換だけを使い、1回の走査で行います。Sort Colorsは、0、1、2を使った同じ問題で、その解法は3つのポインターによる分割です。
Sort Colors の時間計算量と空間計算量は何ですか？
1回の走査で解く方法は、各ステップで未読部分を1セルずつ縮めるため、O(n)時間で実行されます。追加の領域としてO(1)を使用します。交換用の一時値と3つのインデックスです。カウントソートも同じ計算量ですが、配列を2回読み取ります。
Sort Colors の回答として計数ソートは適切ですか？
時間計算量 O(n)、空間計算量 O(1) の条件を満たし、多くの面接官は最初の回答としてこれを受け入れます。次に、1回の走査でできる方法を尋ねられると考えておきましょう。色が多数ある場合は、分割では3つのグループにしか分けられないため、カウントする方法のほうが適しています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def sortColors(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, 1, 0, 2, 0, 1, 1]
期待される出力
[0, 0, 1, 1, 1, 2, 2]