やあ、みんな！この記事では、数字のリストに欠けている要素や繰り返しの要素を見つけるという簡単な問題を理解することになります。
例を通して問題を理解しましょう。
n = 6について、以下の数字のリストを考えてみましょう。
| — | — | — | — | — | — |
| 1 | 2 | 4 | 5 | 5 | 6 |
欠番は1,2,3……nのうち存在しない数、繰返し数はその要素に2回出現する数であろう。
上記の場合、欠番は3、繰り返し数は5となる。
実際の結果は次のようになるはずだ。
1 2 3 4 5 6 のようにすれば、繰り返し数と欠番がなくなります。
こちらもお読みください。
手動で欠落要素や繰り返し要素を見つける
さて、手動で行う方法は、リストを1回巡回して各数字のカウントをチェックすることです。
いずれかの数のカウントが2*nに等しい場合、繰り返し数が見つかり、次に要素を走査して1、2、3、…と各数の出現をチェックします。
もし、それらの数字のいずれかが存在しなければ、その数字を欠損数として返す。
この方法の問題点は、時間がかかること、単純な問題に対して手順が多すぎること、そして、もっと良い方法で行えることです。
欠損要素や繰り返し要素を見つけるためのより良い方法
そこで、ある要素が訪問済みかどうかを考慮した配列を追加で作成することにします。
配列の大きさはnの値と同じです。
最初はすべての値が 0 (未訪問) で、ある要素が配列内で確認された瞬間に、最終的な配列内の値が 1 (訪問済み) に設定されます。
これは配列の終わりまで続きます．繰り返し数と欠番の2つを計算しなければなりません。
もし、ある時点で、値が設定されている数がすでに設定されていれば、その数は繰り返し数であることを意味します。
欠損数を計算するために、最後にもう一度最終配列を走査して、最終配列のどの数値の値がまだ0であるかを調べます。
これは、その数値が一度も現れていないことを意味し、したがってそれは配列の欠損数であることを意味します。
2つの値を持つリスト形式で返します。
1つ目は繰り返しの数、2つ目は欠番の数です。
Pythonで実装する
これでお分かりいただけたかと思います。
それでは、欠落要素や繰り返し要素を見つけるためのコードの実装と、その出力例を見てみましょう。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def find_miss_repeat(arr,n):
final_array = [0 for i in range(n)]
l = [0,0]
for i in arr:
if(final_array[i-1]==1):
l[0] = i
else:
final_array[i-1] = 1
for i in range(len(final_array)):
if(final_array[i]==0):
l[1] = i+1
return l
x = find_miss_repeat([1,2,4,5,5,6],6)
print("Repeating Number: ",x[0])
print("Missing Number: ",x[1])
|
このコードの出力は以下の通りです。
Repeating Number: 5
Missing Number: 3
|
まとめ
コンセプトはご理解いただけたでしょうか。
素朴な方法と迅速な方法の両方を使って、自分で試してみてください。
同じロジックはすべてのプログラミング言語にも適用できます。
チュートリアルを読んでいただき、ありがとうございました。