バケット（配列編）

バケット（配列編）

バケット はあらかじめデータがとりうる値を、すべての容器(バケット)に順番どおりに並べ用意しておくアルゴリズムです。

バケット を使うと次のようなさまざまな問題に簡単に解を出すことができます。

• 配列にある値が含まれるかどうかを判定できる。
• 配列に含まれる値が何種類あるかわかる。
• 配列の要素がすべて異なるかどうかを判定できる。

[問題]

Ｎ個の正の整数があります。

この中に含まれる数値の種類の個数を求めて下さい。

[条件]

・各数字は、1以上10以下の整数

解法・ソースコード

数字の範囲は10以下なので、サイズが11の配列を準備します。（配列のインデックスが0から10の整数を表す）

次に入力の数字ごとに配列に1を設定していきます。（その数字が存在したことを表す）

最終的にこの配列の合計値が、数値の種類の個数を表すことになります。

[Google Colaboratory]

#---------- 入力例 ----------
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9]
#----------------------------
# バケット（全体を0で初初期化）範囲 0～10
bucket = [0] * 11

# 入力リストからバケットを作成
for l in lst:
    bucket[l] = 1

print('バケット：', bucket)
print('解（数値の種類）：', sum(bucket))

[実行結果]

バケット： [0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]

解（種類の個数）： 8

解は 8 となり、入力の数字の種類が 8種類 であることが確認できました。