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

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

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

题解

方法1：将数组排序，从头遍历数组，若两个元素相等返回。

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

方法2：使用哈希表记录数组中每个数出现的次数，若某个数出现次数大于1次，返回该数。

    public int findRepeatNumber(int[] nums) {
        int[] count = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
            if (count[nums[i]] > 1) return nums[i];
        }
        return 0;
    }

方法3：原地操作数组
如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture

    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return 0;
    }

方法4：也是原地操作，把数字对应位置上的元素变成负数。若某个位置上的数变成了负数，说明有两个数指向同一个位置，即出现了重复的数。

    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[Math.abs(nums[i])] < 0) return Math.abs(nums[i]);
            nums[Math.abs(nums[i])] *= -1;
        }
        return 0;
    }