最初に、効率的なアルゴリズムの概要を説明します。その後、具体的なコード例をいくつか示します。
アルゴリズムの概要:
- 配列を順番にスキャンし、要素を順に処理します。
- 処理中の要素が以前に処理された要素と重複している場合、重複値が見つかったとして処理を終了します。
- 重複が見つからない場合、処理中の要素を記録します。
- 配列の終端まで処理が終わるか、重複が見つかるまでステップ1-3を繰り返します。
以下に、このアルゴリズムを使用したコード例を示します。
def find_first_duplicate(arr):
visited = set()
for num in arr:
if num in visited:
return num
visited.add(num)
return None
# 使用例
array1 = [1, 2, 3, 4, 5, 6, 3] # 3が重複している
array2 = [1, 2, 3, 4, 5, 6, 7] # 重複なし
result1 = find_first_duplicate(array1)
result2 = find_first_duplicate(array2)
print("重複値:", result1) # 出力: 3
print("重複値:", result2) # 出力: Noneこのコードでは、visitedというセットを使用して、配列をスキャンしながら処理中の要素を記録します。もし処理中の要素がすでにvisitedに存在していれば、それは重複値であるため、その要素を返します。重複が見つからない場合はNoneを返します。
このアルゴリズムは、配列を一度だけスキャンするだけで最初の重複値を見つけることができます。時間計算量はO(n)であり、非常に効率的です。
この方法を使用することで、1からnまでの整数の配列内で最初の重複値を見つけることができます。