set で重複を除去する
「もう出た値か」を配列に聞くと、毎回全部なめる
重複を取り除きたいとき、真っ先に思いつくのは「結果の配列に既に入っているか調べて、入っていなければ足す」というやり方です。
Python
result = []
for v in tags:
if v not in result:
result.append(v)これは正しく動きます。ただし v not in result の 1 行が曲者で、結果の配列を先頭から順に見に行きます。結果が 5000 件まで育っていれば、1 回の質問に 5000 回の比較です。
tags が 1 万件なら、比較の合計はおよそ 5000 万回。件数が 10 倍になれば 100 倍になる、あの増え方です。重複除去そのものは単純な作業なのに、「あるかどうか」を聞く相手が悪い せいで重くなっています。
「あるかどうか」だけを答える箱
そこで、位置も順番も覚えない代わりに、あるかないかだけを一瞬で答える 箱を使います。
Python
seen = set()
seen.add("tokyo")
seen.add("osaka")
seen.add("tokyo")
print(len(seen)) # 2 同じものは 2 度入らない
print("osaka" in seen) # True
print("kyoto" in seen) # Falsein の答えが返るまでの時間は、中に何件入っていても変わりません。値そのものから置き場所を計算して、そこだけを見に行くからです。1 万件でも 100 万件でも一定です。
配列で 5000 万回かかっていた作業が、1 万回の追加で終わります。
並び順は、あとから決め直す
代わりに手放したものがあります。順番 です。
この箱は「入っている」ことしか覚えていないので、取り出したときに並ぶ順序は当てにできません。決まった順序で返したいなら、取り出したあとに自分で並べ直す必要があります。
並べ直すときは、数値を数値として比べているか確かめてください。JavaScript の既定の並べ替えは、中身を文字として比べます。
JavaScript
console.log([3, 20, 100].sort()); // [100, 20, 3]
console.log([3, 20, 100].sort((a, b) => a - b)); // [3, 20, 100]"100" は "20" より前、という文字どうしの比較になっています。数値の配列を並べるときは、比べ方を自分で渡します。
要件
- 戻り値は重複のない昇順ソート済み配列
- set / HashSet / map を使い、平均 O(n) で重複除去する (O(n^2) の二重ループは避ける)
- 入力配列の順序は気にせず、結果は必ず昇順
入出力例
uniqueValues([3,1,2,1,3]) → [1,2,3]
uniqueValues([5,5,5,5]) → [5]
uniqueValues([4,2,1,3]) → [1,2,3,4]
uniqueValues([7]) → [7]
uniqueValues([1,2,3,2,1,4,5,4]) → [1,2,3,4,5]
uniqueValues([-1,0,-1,2,0]) → [-1,0,2]ヒント
編集 ゆめさく編集部