問題
整数のnums をnums の
- 新しい
並びを 作らず、 受け取った numsの中で 入れ替えます - 入れ替え
終わったら、 最後に その numsを返します。 確かめは 戻り値で見ます numsの長さは 0 以上 10000 以下、 値は どれも 絶対値が 10 億以下です
入力と出力の例
例 1
入力
nums = [0, 4, 0, 7, 2]出力
[4, 7, 2, 0, 0]例 2
0 でない
入力
nums = [5, 0, -3, 0, 0, 1]出力
[5, -3, 1, 0, 0, 0]例 3
0 が 1 つも
入力
nums = [9, 8, 6]出力
[9, 8, 6]面接での聞かれ方
面接では、
- 「配列の 0 を
末尾に 移してください。 ほかの 数の 順は 保ってください」 - 「追加の
配列を 使わずに できますか？」と、 記憶の 使い方を 条件に 足される ことがあります - 書き終えた
あとに 「書き込みの 回数を 減らせますか？」と 聞かれる こともあります
新しい
まず
段 1
まずは
段 2
新しい
段 3
そこで
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def move_zeros(nums):
n = len(nums)
write = 0
for read in range(n):
if nums[read] == 0:
continue
tmp = nums[write]
nums[write] = nums[read]
nums[read] = tmp
write += 1
return numsJavaScript
JavaScript
function moveZeros(nums) {
const n = nums.length;
let write = 0;
let read = 0;
while (read < n) {
if (nums[read] !== 0) {
const tmp = nums[write];
nums[write] = nums[read];
nums[read] = tmp;
write++;
}
read++;
}
return nums;
}書き込む指 write よりwrite から
計算量
- 時間は O(n) です。
読む指が 並びを 前から 1 回なめるだけで済みます - 使う
記憶は O(1) です。 指 2 つと、 入れ替えに 使う 1 つの 置き場だけです - 段 1 の
書き方は、 時間は O(n) ですが、 記憶が O(n) 要ります。 段 2 の 書き方は、 記憶は O(1) でも 時間が 最悪 O(n²) になります
よく
- 0 を
見つけたら 消して 末尾に足す。 繰り返しの 途中で 並びの 長さや 位置が 動き、 数を 読み飛ばします。 Python の removeや JavaScript のspliceは、それ自体も 中で 数を ずらすので 遅くなります - 入れ替えずに
上書きだけして、 0 を 埋め忘れる。 0 でない 数を 前へ写すだけの 書き方なら、 最後に writeから後ろを 0 で 埋める 手順が要ります - 並べ替えで
済ませる。 「0 かどうか」で 並べ替えると、 0 でない 数の 順が 保たれない 書き方に なりやすく、 時間も O(n log n) かかります
面接での
書き始める
「0 でない
数と 0 を 別の 並びに 集めれば 簡単ですが、 追加の 記憶を 使わない 条件なので、 指を 2 つ 使います。 読む指で 前から 見て、 0 でない 数を 書き込む指の 位置と 入れ替えます。 時間は O(n)、 記憶は O(1) です。」
書き終えたら、
「例 1 の
[0, 4, 0, 7, 2]でたどります。 最初の 0 は 飛ばします。 4 で 書き込む位置の 0 番と 入れ替えて [4, 0, 0, 7, 2]です。次の 0 も 飛ばし、 7 を 1 番と 入れ替え、 2 を 2 番と 入れ替えると [4, 7, 2, 0, 0]になります。」