请教下该从数组中删除重复的元素,并考虑算法的执行效率?

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

扬帆大鱼
浏览 116回答 2
2回答

潇湘沐

最快的算法肯定是O(n)具体做法是:1,准备一个HashMap或者HashTable2,循环你的输入数组,判断他是否在HashMap中,如果不是,输出,并且加入到HashMap中(比如:Map.put(1,true)),如果是在HashMap中则什么都不做。因为HashMap的读取和设置是O(1)的时间复杂度,所以加上循环整体的时间复杂度也是O(n)

宝慕林4294392

难点1)数组,如果是链表可能会比较容易些:也就是移走重复的后,不能留下空洞2)去重:应该是只需要扫描数组一遍,否则性能不太好.3)排序的稳定,也就是顺序保持不变.方案:使用Bitmap来依次检查重复         如果重复, 则后面所有的数组节点往前移一个位置. 具体的代码可以参考ArrayList.remove()         如果没有重复,遍历数组下一节点评价:只需要引入一个Bitmap,内存消耗非常小检索去重,性能很快,只需要一次运算即可不需要使用一个新的数组来对考
打开App,查看更多内容
随时随地看视频慕课网APP