モジュロ法のアイデアは、配列内のすべての数値を一つずつ処理し、その数値の出現回数をカウントすることです。具体的な手順は次のとおりです。
-
配列内のすべての数値に対して、モジュロ演算を行います。具体的なモジュロ値は、配列内の数値の範囲に基づいて適切に選択します。例えば、配列内の数値が0から9の範囲であれば、モジュロ値は10とします。
-
各数値のモジュロ結果をカウンター配列に格納します。カウンター配列の要素は、数値のモジュロ値に対応します。
-
カウンター配列を走査し、出現回数が1である要素のモジュロ値を取得します。
-
もとの配列を再度走査し、2回目のモジュロ演算を行い、得られたモジュロ値と比較します。一致する数値が見つかれば、それは繰り返しのない数値です。
以下に、Pythonでの実装例を示します。
def find_unique_number(arr):
mod_value = len(arr) + 1
counter = [0] * mod_value
for num in arr:
counter[num % mod_value] += 1
for num in arr:
if counter[num % mod_value] == 1:
return num
return None
# 使用例
array = [1, 2, 3, 4, 5, 1, 2, 3, 4]
unique_number = find_unique_number(array)
print(unique_number) # 繰り返しのない数値である5が出力されますこの方法は、モジュロ演算と配列の走査を2回行うため、計算量はO(n)です（nは配列の要素数）。そのため、効率的な方法と言えます。
以上が、モジュロ法を使用して配列内の繰り返しのない数値を見つける方法の説明とコード例です。ご参考までにお使いください。