如何计算列表中的唯一项？

Question

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

例如，假设我有 {1, 3, 3, 4, 1, 3}，我想获取数字 3，它代表列表中唯一项目的数量（即 |A|=3，如果 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”）并且 这就是问题所在。

知道如何解决这个问题吗？

Answer 1

将项目添加到 HashSet，然后在完成后检查 HashSet 的大小。
假设您有一个好的哈希函数，则时间复杂度为O(n)。

Answer 2

您可以检查该号码后面是否有重复的号码。如果不增加 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 的散列键的计数。

Answer 3

使用像归并排序或堆排序这样的不错的排序算法对其进行排序（最坏情况都是 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

Answer 4

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

Answer 5

保留字典并在循环中添加计数

这就是 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 方式，但据我了解，问题很普遍；)