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

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个重复数字3(过度计算最后的"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.