問題
作業のnums を
- 新しい
並びを 作らず、 受け取った numsの中身を 入れ替えて、 その numsを返します - 言語に
備わった 並べ替え ( sort) は使いません - 並びを
前から 1 回なめるだけで、 決まった 数の 置き場だけを 使って 解いてください numsの長さは 1 以上 300 以下です
入力と出力の例
例 1
入力
nums = [2, 0, 1, 2, 1, 0]出力
[0, 0, 1, 1, 2, 2]例 2
2 が 1 つも
入力
nums = [1, 1, 0]出力
[0, 1, 1]例 3
後ろから
入力
nums = [2, 2, 2, 0]出力
[0, 2, 2, 2]面接での聞かれ方
面接では、
- 最初に
sortで済ませると、 「備わった 並べ替えを 使わずに お願いします」と 言われます - 数を
数えて 書き直す 書き方を 出すと、 「並びを 1 回だけなめて 済ませられますか？」と続きます - 書き終えた
あとに 「後ろと 入れ替えた とき、 真ん中の 指を 進めないのは なぜですか？」と、 指の 動かし方の 理由を 聞かれます
ここで
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
1 回でlo、mid、hi でlo よりlo から mid のmid から hi まではhi よりlo と mid がhi が
段 3
mid のlo のlo と mid を 1 つmid だけhi のhi を 1 つ戻します。mid は
段 4
mid が hi をmid <= hi のmid < hi に
解答
Python
Python
def sort_colors(nums):
lo = 0
mid = 0
hi = len(nums) - 1
while mid <= hi:
v = nums[mid]
if v == 0:
swap(nums, lo, mid)
lo += 1
mid += 1
elif v == 1:
mid += 1
else:
swap(nums, mid, hi)
hi -= 1
return nums
def swap(a, i, j):
a[i], a[j] = a[j], a[i]JavaScript
JavaScript
function sortColors(nums) {
let lo = 0;
let mid = 0;
let hi = nums.length - 1;
while (mid <= hi) {
const v = nums[mid];
if (v === 0) {
swap(nums, lo, mid);
lo++;
mid++;
} else if (v === 1) {
mid++;
} else {
swap(nums, mid, hi);
hi--;
}
}
return nums;
}
function swap(a, i, j) {
[a[i], a[j]] = [a[j], a[i]];
}Go
Go
func sortColors(
nums []int,
) []int {
lo, mid := 0, 0
hi := len(nums) - 1
for mid <= hi {
switch nums[mid] {
case 0:
swap(nums, lo, mid)
lo++
mid++
case 1:
mid++
default:
swap(nums, mid, hi)
hi--
}
}
return nums
}
func swap(a []int, i, j int) {
a[i], a[j] = a[j], a[i]
}0 とmid もlo のlo と mid が
計算量
- 時間は O(n) です。
1 回まわる ごとに、 midが 1 つ進むか hiが 1 つ戻るかして、 「まだ見ていない」 区画が 必ず 1 つ縮みます - 使う
記憶は O(1) です。 指 3 本だけで、 受け取った 並びの 中で 入れ替えます - 数えて
書き直す 書き方も O(n) と O(1) ですが、 並びを 2 回なめます。 この 書き方は 1 回で済みます
よく
- 2 と
入れ替えた あとに midも進める。 後ろから持ってきた 値が 0 だと、 それを 前へ 送らずに 通り過ぎます。 例 3 の [2, 2, 2, 0]で、0 が 前に 来なくなります - 止める
条件を mid < hiにする。midとhiが同じ 位置に 来た とき、 その 1 つを まだ 見ていません。 [1, 0]のような短い 並びで 0 が 後ろに残ります hiの始まりを len(nums)にする。 末尾の 1 つ外を指すので、 最初の 入れ替えで 並びの 外を 読みます。 hiは「2 の 区画の 1 つ手前」なので、 末尾の 位置から始めます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「数えて
書き直せば O(n) ですが 2 回なめます。 1 回で 済ませる ため、 3 本の 指で、 前から 0 の 区画、 1 の 区画、 まだ 見ていない 区画、 2 の 区画に 分けます。 真ん中の 指の 値が 0 なら 前と 入れ替えて 両方進め、 1 なら 進めるだけ、 2 なら 後ろと 入れ替えて 後ろの 指を 戻します。 時間は O(n)、 記憶は O(1) です。」
書き終えたら、
「例 3 の
[2, 2, 2, 0]をたどります。 真ん中の 指の 2 を 末尾の 0 と 入れ替えて [0, 2, 2, 2]、後ろの 指を 戻します。 真ん中の 指は 進めずに もう 一度見ると 0 なので、 前の 指と 同じ 位置で 入れ替え、 両方を 進めます。 残りの 2 も、 後ろの 指の 位置と 入れ替えて 後ろの 指を 戻す、を くり返し、 真ん中の 指が 後ろの 指を 越えた ところで 終わりです。」