【剑指Offer03】数组中的重复数字

数组中的重复数字

题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

方法一：Set集合
将数组中的数字逐一添加到set集合中，如果set集合已经存在当前数字，说明重复。

class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet set = new HashSet<>();
        for(int n : nums){
            if(set.contains(n)) return n;
            else set.add(n);
        }
        return -1;
    }
}

方法二：数组排序
将num数组排序，从下标为1的数字开始比较，如果当前数字和前一个数字相等说明重复

class Solution {
    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 -1;
    }
}

方法三：数组下标
题目中提到长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内，说明当不存在重复数字的时候，数字和下标可以一一对应。将各个数字放入数组中对应的下标位置上，若该下标上的数字和当前数字相等说明重复。

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