一、题目描述
======
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
二、思路分析
======
考察点
三、代码+解析
=======
初版
--
public int findRepeatNumber(int[] nums) {
//构建hash表 。 Java中Map天生的Hash表
Map<Integer, Object> map = new HashMap<>();
for (int num : nums) {
//已经在hash表中存在的说明数据重复
if (map.containsKey(num)) {
return num;
}
//没有重复的数据需要添加到hash表中
map.put(num, num);
}
return 0;
}
首次升级
优化落地
HashMap
快的多,所以在速度上应该也会快很多的public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return 0;
}
再次升级
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int index =i;
while (index != nums[index]) {
index = nums[index];
}
if (index != i) {
return index;
}
}
return 0;
}
最终升级
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (i != nums[i]) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
nums[i] = nums[i] ^ nums[nums[i]];
nums[nums[i]] = nums[nums[i]]^nums[i];
nums[i] = nums[i] ^ nums[nums[i]];
}
}
return 0;
}
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。