从数组中删除重复的元素，并考虑算法的执行效率

0 0

从数组中删除重复的元素，并考虑算法的执行效率0

写一个函数来从数组中删除重复的对象。维持秩序。例如，如果输入的数组[ 1，5，4，2，7，2，6，5 ]，结果应该是[ 1，5，4，2，7，6 ]。实施时应执行速度的优化。

2014年8月06日 14:57

郑云飞
1
0 0 11

采纳的答案

最快的算法肯定是O(n)
具体做法是：
1，准备一个HashMap或者HashTable
2，循环你的输入数组，判断他是否在HashMap中，如果不是，输出，并且加入到HashMap中（比如：Map.put(1,true)），如果是在HashMap中则什么都不做。

因为HashMap的读取和设置是O(1)的时间复杂度，所以加上循环整体的时间复杂度也是O(n)

2014年8月06日 17:34

red008
217
0 1 24

添加评论

0 0

首先我们要明白目的就是去重，逻辑就是从头到尾挨个看其中一个元素有没有重复。
那么一般有两个逻辑

从头到尾挨个遍历，发现后面有重复的就移除，并移动全部元素（时间代价很高）
利用散列原理的数据结构，另外构建该结构，并利用散列值来去重。比如java中的hashtable。

你题中只要求效率，这个一般就指的不考虑空间效率了，那么你就可以使用java中hashtable 或者其他语言中的类hashtable的数据结构。

注：hashtable 或者散列结构的数据结构，其存储地址是随机不连续且根据存储的值计算出来的因此在查找某一个元素的时候的速度非常快，因为不用遍历。

最后把hashtable转成数组，或者不转直接拿来用。

2014年8月07日 09:11

xuelianbobo
38
0 0 5

添加评论

0 0

难点
1)数组,如果是链表可能会比较容易些:也就是移走重复的后,不能留下空洞
2)去重:应该是只需要扫描数组一遍,否则性能不太好.
3)排序的稳定,也就是顺序保持不变.

方案:
使用Bitmap来依次检查重复
如果重复, 则后面所有的数组节点往前移一个位置. 具体的代码可以参考ArrayList.remove()
如果没有重复,遍历数组下一节点

评价:
只需要引入一个Bitmap,内存消耗非常小
检索去重,性能很快,只需要一次运算即可
不需要使用一个新的数组来对考