首页 / 面试 / 面试题3.2：不修改数组找出重复的数字
面试题3.2：不修改数组找出重复的数字
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题3.2：不修改数组找出重复的数字，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1158字，纯文字阅读大概需要2分钟。
内容图文
题目描述：在一个长度n+1的数组里的所有数字都在1～n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
解法一：利用辅助数组
创建一个长度为n+1的辅助数组，将原数组的每个下标处元素的值作为辅助数组的下标，并使辅助数组的下标处元素的值加1，当值大于1时，说明出现重复。
新数组:
索引 值
0 0
1 0
2 0
3 0
4 0
5 0
当找到第一个重复元素3时
新数组：
索引 值
0 0
1 0
2 1
3 1
4 1
5 1
到第5个下标时，
索引3 --> 2 说明此时原数组下标i处产生了重复元素。
此方法需要使用额外空间O(N)。
解法二：二分查找，分致思想。
根据题目描述，长度为8的数组，所有数字都在1～7之间。使用中间数字4，将1～7分成两段，一段是1～4，一段是5～7。
统计1～4这4个数组在数组中出现的次数，如果>4次，说明重复的数字就在这段区域，再继续二分。如果<4次，则在另一段区间，对另一段区间进行二分。
public
static
int getDuplication(int[] nums) {
if (nums == null || nums.length < 0) {
return -1;
}
int start = 1;
int end = nums.length - 1;
while (start <= end) {
int mid = ((end - start) >> 1) + start;
int count = 0;
//寻找该区间数字在数组中出现的次数for (int num : nums) {
if (num >= start && num <= mid) {
count++;
}
}
//区间只剩一个数字if (end == start) {
//如果该数字出现了两次，就是重复if (count > 1) {
return start;
} else {
break;
}
}
//如果该区间中元素出现的个数，大于区间的最大值，说明该区间存在重复的数字if (count > mid - start + 1) {
//在分割后的左边区间内
end = mid;
} else {
//在分割后的右边区间
start = mid + 1;
}
}
return -1;
}
原文：https://www.cnblogs.com/pxy-1999/p/13734421.html
内容总结
以上是互联网集市为您收集整理的面试题3.2：不修改数组找出重复的数字全部内容，希望文章能够帮你解决面试题3.2：不修改数组找出重复的数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。