剑指offer:1.找出数组中重复的数(java版)

时间:2021-08-03 09:03:43

数组中重复的数:
题目:找出数组中重复的数,
题目描述:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。
数组中某些数字是重复的,但不知道有几个数字是重复的。
也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如,如果输入长度为7的数组{2,3,1,0,2,5,3},
那么对应的输出是重复的数字2或者3。

分析:

<一>
首先进行重新排序
然后从头进行扫描即可。
1.比较下标,如果下标index等于数组num[index]继续比较下一个
如果不等于:将index与num[index]比较:如果相等则这个数是重复的;如果不相等,
将index与num[index]交换,然后继续比较.....
如:[2,3,1,0,2,5,3]---->[1,3,2,0,2,5]----->[3,1,2,0,2,5,3]
------>[0,1,2,3,2,5]到扫到2时由于下标4与数值2不一致,再比较
2与下标为2中的数发现相等,即可以得到重复的数;

剑指offer:1.找出数组中重复的数(java版)

运行结果如下:

剑指offer:1.找出数组中重复的数(java版)

<二>

当然这个题也可以用hashmap解决:

遍历数组,采用hashmap存放每个元素,其中元素作为key存储,value为0。
当前遍历元素插入hashmap时,先检查hashmap中是否已经存在同样的key。
若存在,记录下该值,返回true;若不存在,存入map中,继续遍历,直到数组结束,返回false.、

<三>

如果要求不修改数组找出重复的数:

按照二分查找的思路,将1-n分成两半,假如将1-n分成1-m和m+1到n。如果1~m中的数字的数目超过m,那就说明有重复数字;
否则,另一半中一定有重复的数字。我们可以继续把包含重复数字的区间继续二分,直到找到一个重复的数字。