0

入力:個別の要素A[1..n]のみを持つソートされていない整数配列。O(d) :(d < < n)

出力:正確に 2 回出現したすべての要素。

を使用するアルゴリズムと を使用するアルゴリズムの 2 つを求めO(Nd)ますO(Nlogd)。最大数は非常に大きくなる可能性があるためn、頻度をカウントするサイズの配列はお勧めできません。何か考えはありますか？

明確にするために、「O(d) :(d < < n)異なる要素のみを含む」とは、他のすべての要素 (それらの要素を除くO(d)) が 2 回以上出現したことを意味します。

4

3 に答える 3

1

O(nd)基本的に、可能なすべての要素（O(d)それらの要素）を繰り返し、繰り返し回数を数えます。各反復は O(n)

O(nlogd)各要素が 1 回の反復でリストに表示される回数をカウントするヒストグラム( )を作成することです。map:int->intマップは、バランスのとれた二分探索木に基づいていO(nlogd)ます。ツリーの代わりにハッシュ マップO(n)を使用すると、平均的なケース (ただし、O(nd)最悪のケース)まで増やすことができることに注意してください。

疑似コード- O(nlogd):

map <- new tree map
for each element x in list:
 if x is in map:
     map.put(x,map.get(x)+1)
 else:
     map.put(x,1)
for each (key,value) in map:
  if value == 2:
     print key
于 2013-01-03T11:06:43.577 に答える
0

配列をソートします。O(nlogn) 配列をスキャンして、2 回だけ出現した要素を見つけます。O(n)

繰り返し要素が並んで表示されます。

O(n)+O(nlogn)。

于 2013-01-03T11:05:24.037 に答える