剑指 Offer 03.数组中重复的数字

题目描述

原题

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:23

限制:

2 <= n <= 100000

题解

暴力求解

class Solution {
public int findRepeatNumber(int[] nums) {
for(int i = 0;i<nums.length-1;i++){
for(int j = i+1;j<nums.length;j++){
if(nums[i]==nums[j]){
return nums[i];
}
}
}
return -1;
}
}

哈希查找

class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num:nums){
if(!set.add(num)){
return num;
}
}
return -1;
}
}

原地交换

class Solution {
public int findRepeatNumber(int[] nums) {
//长度为n的数组 索引范围是0~n-1
//根据题目中所有数字都在0~n-1之间
//我们可以在0的位置存0 1的位置存1 n的位置存n
//存入的时候判断该位置 索引是否与值相等 如果已经相等说明重复了
int length = nums.length;
int i = 0;
//遍历
while(i<length){
//索引与值比较 不相等 则存入当前值
if(nums[i]!=i){
//查询值作为索引对应位置的值 是否与索引相同
if(nums[nums[i]]==nums[i]){
return nums[i];
}else{
//不相等进行交换
int tmp = nums[i];
nums[i] = nums[tmp];
//注意这里不要写一定是nums[tmp]不是nums[nums[i]]
nums[tmp] = tmp;
}
}
i++;
}
return -1;
}
}