問題
並び items をitems の
- 入れ子の
深さに 決まりは ありません。 ただし、 一番深い ところでも 100 段までです - 空の
並びが 中に 入っている こともあります。 空の 並びからは 何も 取り出しません - 中に
ある 整数の 数は、 全部で 0 以上 10000 以下です
入力と出力の例
例 1
入力
items = [1, [2, 3], 4]出力
[1, 2, 3, 4]例 2
深さが
入力
items = [[5, [6, [7]]], 8, [9]]出力
[5, 6, 7, 8, 9]例 3
空の
入力
items = [[], [-1, []], 0]出力
[-1, 0]面接での聞かれ方
面接では、
- 「入れ子に
なった 配列を 平らに してください」 - 書き終えた
あとに 「入れ子が とても 深いと どうなりますか？」と 聞かれる ことがあります - 「再帰を
使わずに 書けますか？」と、 別の 書き方を 求められる こともあります
深さに
まず
段 1
まず、items を
段 2
深さが 2 段、
段 3
そこで、
段 4
結果を
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def flatten(items):
out = []
def walk(xs):
for x in xs:
if type(x) is list:
walk(x)
else:
out.append(x)
walk(items)
return outJavaScript
JavaScript
function flatten(items) {
const out = [];
function walk(xs) {
for (const x of xs) {
if (Array.isArray(x)) {
walk(x);
} else {
out.push(x);
}
}
}
walk(items);
return out;
}補助のwalk は、out に
計算量
- 時間は O(n) です。
ここでの n は、 整数と 並びを 合わせた 中身の 数です。 どの 中身も 1 回ずつ見ます - 使う
記憶は、 答えの 並びの O(n) と、 呼び出しが 重なる 深さ d の 分の O(d) です - 呼び出しは、
深さの 分だけ重なります。 Python は 既定で 約 1000 段を 超えると 止まるので、 この 問題の 100 段までなら 心配ありません。 深さに 決まりが 無いなら、 自分で スタックを 持つ 書き方に変えます
よく
- 止まる
条件を 書き忘れる。 整数の ときに 自分を 呼ばずに 足す、という 分かれ道が 止まる 条件です。 これが 無いと、 整数を 並びとして 扱おうとして 止まります - 呼び出しの
結果を 受け取り忘れる。 補助の 関数を 使わずに 書くなら、 flatten(x)が返した 並びを 答えに つなげる 必要が あります。 呼ぶだけで 捨てると、 深い所の 整数が消えます - 並びか
どうかを 長さで 見分ける。 Python の lenや JavaScript のlengthで見分けようと すると、 整数で 例外が 出たり、 空の 並びを 取り違えたりします。 Python は isinstance(x, list)、JavaScript は Array.isArray(x)で見分けます
面接での
書き始める
「並びの
中の 並びも、 平らに するという 同じ 問題なので、 再帰で 書きます。 整数なら そのまま 答えに 足し、 これが 止まる 条件です。 並びなら 同じ 関数に 任せます。 答えの 並びは 1 つだけに して、 写す手間を 増やさないようにします。」
書き終えたら、
「呼び出しは
入れ子の 深さの 分だけ重なります。 今回は 100 段までなので 大丈夫ですが、 もっと 深くなるなら、 自分で スタックを 持って繰り返しで 書く 形に 変えます。」