2

リスト内の一意のアイテムの数をどのように数えますか?

たとえば、{1, 3, 3, 4, 1, 3} があり、リスト内の一意のアイテムの数を表す数値 3 を取得したいとします (つまり、A={1, 3 の場合 |A|=3) 、4})。誰かがこれにどのアルゴリズムを使用しますか?

私は二重ループを試しました：

for firstItem to lastItem
  currentItem=a
  for currentItem to lastItem
    currentItem=b
    if a==b then numberOfDublicates++
uniqueItems=numberOfItems-numberOfDublicates

実際に必要な回数よりも多くの重複をカウントするため、これは機能しません。最初の例では、次のようになります。

  1. 最初のループでは、リストの番号 1 に対して +1 個の重複がカウントされます。
  2. 2 番目のループでは、リストの番号 3 に対して +2 個の重複がカウントされます。
  3. 3 番目のループでは、番号 3 の +1 重複を再度カウントし (最後の「3」を過大評価)、ここで問題が発生します。

これを解決する方法について何か考えはありますか？

4

5 に答える 5

11

項目を HashSet に追加し、終了後に HashSet のサイズを確認します。
適切なハッシュ関数があると仮定すると、これはO(n).

于 2011-03-14T14:19:19.423 に答える
6

番号の後に重複がないかどうかを確認できます。uniqueCount をインクリメントしない場合:

uniqueCount = 0;
for (i=0;i<size;i++) {
  bool isUnique = true;
  for (j=i+1;j<size;j++)
     if (arr[i] == arr[j] {
       isUnique = false;
       break;
     }
  }
  if(isUnique) {
    uniqueCount ++;
  }
}

上記のアプローチはO(N^2)、時間的およびO(1)空間的です。

もう 1 つの方法は、入力配列を並べ替えて、重複する要素を隣り合わせにしてから、隣接する配列要素を探すことです。このアプローチはO(NlgN)時間とO(1)空間にあります。

追加スペースの使用が許可されている場合は、ハッシュを使用してO(N)時間とスペースでこれを行うことができます。O(N)ハッシュのキーは配列要素で、値はその頻度です。

ハッシュの最後に、 の値を持つハッシュ キーのみのカウントを取得できます1。

于 2011-03-14T14:29:14.720 に答える
2

mergesort や heapsort (どちらも最悪の場合は O(n log n)) のような適切な並べ替えアルゴリズムを使用して並べ替え、並べ替えられたリストをループします。

sorted_list = sort(list)
unique_count = 0
last = sorted_list[0]

for item in sorted_list[1:]:
  if not item == last:
    unique_count += 1
  last = item
于 2011-03-14T14:18:45.727 に答える
1 
list.sort();
for (i = 0; i < list.size() - 1; i++)
  if (list.get(i)==list.get(i+1)
    duplicates++;
于 2011-03-14T14:19:49.877 に答える
0

辞書を保持し、ループでカウントを追加

これは、C＃でどのように見えるかです

int[] items = {1, 3, 3, 4, 1, 3};
Dictionary<int,int> dic = new Dictionary<int,int>();
foreach(int item in items)
   dic[item]++

もちろん、C#にはLINQの方法がありますが、私が理解しているように、質問は一般的です;)

于 2011-03-14T14:18:13.330 に答える