2

有人会如何继续计算列表中唯一项目的数量？

例如说我有 {1, 3, 3, 4, 1, 3} 并且我想得到数字 3 代表列表中唯一项目的数量（即 |A|=3 if A={1, 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. 对于第二个循环，它将为列表中的数字 3 计算 +2 个重复项。
  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)空间上的。

另一种方法是对输入数组进行排序，将重复元素彼此相邻，然后查找相邻的数组元素。这种方法是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 回答