跳转至

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

题目描述

原题

找出数组中重复的数字。

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

示例 1：

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

题解

暴力求解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

哈希查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            if(!set.add(num)){
                return num;
            }
        }
        return -1;
    }
}

原地交换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
}