为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

扬帆大鱼 2022-09-17 15:15:07

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

查看完整描述

2 回答

?
潇湘沐

TA贡献1483条经验 获得超6个赞

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

查看完整回答
反对 回复 2022-09-21
?
宝慕林4294392

TA贡献1711条经验 获得超1个赞

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

查看完整回答
反对 回复 2022-09-21
  • 2 回答
  • 0 关注
  • 12 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信