数组中重复的数字

方法一:
先将数组排序,然后顺序扫描数组。直到发现有重复数字;
时间:O(nlogn)
空间:O(l)

方法二:
用一个HashMap,顺序扫描数组,如果HashMap没有包含当前数字,就把这个数字放入HashMap,否则,就为重复数字。
时间:O(n)
空间:O(n)

方法三:
顺序扫描数组,判断当前扫描的每个数字是否满足 numbers[i]=i ,如果不满足,则说明这个数字不在对应的位置上,于是把将这个数字与numbers[numbers[i]]交换,如果扫描某个数字的过程中发现numbers[i]=numbers[numbers[i]],则说明numbers[i]在i 位置和numbers[i]位置出现了两次,所以是重复数字。
时间:O(n)
空间:O(l)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目要求 在一个长度为n的数组里所有数都在0-n之间,数组中存在重复的数,但是不知道几个数字重复了,也不知道数字重...
    小庄bb阅读 3,480评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,351评论 0 33
  • 题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复...
    NoFacePeace阅读 1,098评论 0 0
  • 德国位于欧洲大陆的中间,称得上是欧洲最强的经济体。一提起德国,大家首先想到的就是德国二战的历史,或者就是举世闻名的...
    北方有粗人阅读 5,429评论 10 19
  • 请让我带你到那晚的星空银河,坐在我家门前的门槛上喝一碗春季三月的黄酒,顺便看看我曾经有什么。 三月的春季,暖...
    扬子婠婠阅读 3,613评论 0 2