数组删除重复元素

Question

我有一个未排序的数组,如果存在,删除元素的所有重复项的最佳方法是什么？

例如:

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]

所以在那个操作之后,数组应该是这样的

 a[1,5,2,6,8,9,10,3,4,11]

Answer 1

检查每个元素与其他所有元素

天真的解决方案是检查每个元素与其他元素.即使您只是"前进",这也是浪费并产生O(n ²)解决方案.

排序然后删除重复项

一个更好的解决方案是对数组进行排序,然后将每个元素检查到它旁边的元素以查找重复项.选择有效的排序,这是O(n log n).

基于排序的解决方案的缺点是不维护订单.然而,额外的步骤可以解决这个问题.将所有条目(在唯一排序的数组中)放入具有O(1)访问权限的哈希表中.然后迭代原始数组.对于每个元素,检查它是否在哈希表中.如果是,请将其添加到结果中并将其从哈希表中删除.您将得到一个结果数组,该数组具有原始的顺序,每个元素与第一次出现的位置相同.

线性的整数

如果你正在处理一些固定范围的整数,你可以通过使用基数排序做得更好.例如,假设数字都在0到1,000,000的范围内,则可以分配大约1,000,001的位向量.对于原始数组中的每个元素,您可以根据其值设置相应的位(例如,设置第14位时值为13).然后遍历原始数组,检查它是否在位向量中.如果是,则将其添加到结果数组中并从位向量中清除该位.这是O(n)并且交易时间空间.

哈希表解决方案

这导致我们找到最好的解决方案:排序实际上是一种分心,虽然有用.创建具有O(1)访问权限的哈希表.遍历原始列表.如果它不在哈希表中,则将其添加到结果数组并将其添加到哈希表中.如果它在哈希表中,请忽略它.

这是迄今为止最好的解决方案.那为什么其余的呢？因为这样的问题是关于调整你已经(或者应该)知识的知识,并根据你在解决方案中做出的假设来改进它们.发展解决方案并理解其背后的思想远比反刍解决方案更有用.

此外,哈希表并不总是可用.采用嵌入式系统或空间非常有限的东西.您可以在少数操作码中实现快速排序,远远少于任何哈希表.