キーでグループ化
分け先が 5 つになったら、5 周する気ですか
偶数だけを集めて 1 周、奇数だけを集めてもう 1 周。2 つならまだ我慢できます。しかし「3 で割った余りで分けろ」と言われた瞬間に 3 周、月ごとに分けろと言われたら 12 周です。
分け先がいくつに増えても、配列を読む回数は 1 回で足ります。
入れ物は、出てきたときに作る
JavaScript
// 別題材 — 商品をカテゴリごとに束ねる
const groups = {};
for (const item of items) {
const key = item.category;
if (!groups[key]) groups[key] = [];
groups[key].push(item.name);
}肝は if (!groups[key]) groups[key] = [] の 1 行です。キーがまだ無いところに push しようとしても、押し込む相手がいません。先に空の入れ物を置いてから入れます。数えるときの「無ければ 0 から」と同じ形で、こちらは「無ければ空の入れ物から」です。
こうすれば、分け先がいくつあっても配列を歩くのは 1 周だけになります。
今回の課題は分け先が 2 つと決まっているので、キー付きの表を用意せず、入れ物を 2 つ並べても構いません。表を使うかどうかが目的ではなく、1 周で振り分けきることが目的です。
中身は合っているのに落ちる
今回の課題で落ちる原因の大半は、値ではなく並びです。振り分けた順のまま返すと、[3, 1, 2, 4] から [[2, 4], [3, 1]] が出てきます。中身は正しいのに、奇数側が昇順になっていません。返す前に必ず並べ替えます。
JavaScript で並べ替えるときは、比べ方を渡してください。
JavaScript
[10, 2, 1].sort(); // [1, 10, 2] — 文字列として比べている
[10, 2, 1].sort((a, b) => a - b); // [1, 2, 10]既定の sort は、要素を文字列に直してから並べます。"10" は "2" より前に来るので、数の大小とは違う結果になります。1 桁の数しか無いテストでは気づけないのが、この罠の嫌なところです。
負の数の余りは言語で違う
偶数と奇数の振り分けにも 1 つ落とし穴があります。
- Python の
-3 % 2は1 - JavaScript の
-3 % 2は-1
余りが 1 なら奇数 と書くと、JavaScript では -3 が奇数から漏れて、どちらのグループにも入らなくなります。余りが 0 なら偶数、そうでなければ奇数 と、判定を 1 つだけ書いて残りをまとめるほうが安全です。
空の配列を渡されても、返す形は変わりません。中身が空の入れ物を 2 つ入れて返します。
要件
- 戻り値は
[偶数の昇順リスト, 奇数の昇順リスト]の 2 要素配列 - 1 パスでグループに振り分けてから昇順ソートする (
O(n log n)) - 空配列は
[[], []]を返す
入出力例
groupByParity([3,1,2,4]) → [[2,4],[1,3]]
groupByParity([1,2,3,4,5]) → [[2,4],[1,3,5]]
groupByParity([2,4,6]) → [[2,4,6],[]]
groupByParity([1,3,5]) → [[],[1,3,5]]
groupByParity([10,7,8,3,1]) → [[8,10],[1,3,7]]ヒント
