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

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重复，对于第二循环它将为列表中的第3号计数+2重复，对于E 111第三循环代码>E 212它将计数+1重复(重复数最后一个'3')，问题出现在这里。H 213G 214

知道怎么解决这个问题吗？

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

使用一种体面的排序算法对其排序，如mergesort或堆排序(最坏的情况都是habe (N log ))，并循环排序列表：

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