如何統計列表中的唯一項目？

舉個例子說我有{1,3,4,4,1,3}，我想得到數字3代表列表中唯一項的數量（即| A | = 3，如果A = {1,3,4}）。什麼算法會有人用這個？

我已經tryied雙循環：

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

，因爲它計數重複的次數比實際需要的那不起作用。隨着年初的例子那就是：

對於第一循環將數+1副本列表中的號碼1。
對於第二個循環它將在列表中爲數字3計數+2個重複。
對於第三循環將數+1的重複再次3號（超量的最後一個「3」）和有哪裏出了問題的用武之地。

如何解決這個任何想法？

來源

2011-03-14 Pithikos

保持字典和環加計

這是怎麼會看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-14 14:18:13

排序（二者HABE爲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-14 14:18:45

你可以比'O（n logn）'做得更好。 – SLaks 2011-03-14 14:20:01

將項目添加到HashSet，然後在完成後檢查HashSet的大小。
假設你有一個很好的散列函數，這是O(n)。

來源

2011-03-14 14:19:19 SLaks

這不適用於純C，對吧？因爲我能想到實現這一點的唯一方法是檢查數組中是否存在散列，並給出第二個循環。這比O（n）多。 – Pithikos 2011-03-14 15:47:52

@Pithikos：錯;您可以直接將散列轉換爲數組索引。閱讀哈希表; http://en.wikipedia.org/wiki/Hash_table – SLaks 2011-03-14 15:48:28

任何算法或技術都可以用任何（體面）圖靈語言來實現，儘管它可能需要更多的努力。 _任何東西都可以在純C中完成。 – SLaks 2011-03-14 15:50:00

list.sort(); 
for (i = 0; i < list.size() - 1; i++) 
    if (list.get(i)==list.get(i+1) 
    duplicates++;

來源

2011-03-14 14:19:49 Ishtar

您可以檢查數字後面是否有重複項。如果不是遞增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)。

另一種方法是對輸入數組進行排序，這會將重複的元素相鄰放置，然後查找相鄰的數組元素。這種方法在時間上是O(NlgN)，在空間上是O(1)。

如果您可以使用額外的空間，您可以通過使用散列來完成O(N)時間和O(N)時間。哈希鍵是數組元素，值是它們的頻率。

在散列結束時，您只能得到值爲1的散列鍵的計數。

來源

2011-03-14 14:29:14 codaddict

如何統計列表中的唯一項目？

回答

相關問題