剑指03 找出数组中的重复数字

剑指03 找出数组中的重复数字

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

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

限制：

2 <= n <= 100000

题解

由于这道题中明确的给出了数组中数字的出现范围，而且题目限定中对 n 的大小也做出了限定，因此一种最直接的办法就是开辟另一个数组 a ，利用哈希表的思想进行实现（哈希表的键就是数组的索引，值为数组中数出现的次数），这种方法下的 时间复杂度为 ,空间复杂度为,对应下面的解法一。

那么有没有办法进行进一步的优化呢？这里是有的，我们通过下面的方法二能够进行空间上的优化。由于我们的数组的长度为n, 同时数组中数字的范围为0~n - 1, 那么如果我们的数组中没有出现重复的数字，并且是按照从小到大的顺序排列好的，那么数组i位置上的数字就刚好为i。但是此时由于存在重复的数字那么有些位置上就会有几个数字，而有些位置上又没有数字。按照这个特性我们考虑下面的操作过程：
从头到尾遍历整个数组，

1. 如果数组 i 位置的数字（用 m 表示）满足 i == m 就说明整个数字 m 放置的位置是正确的，继续向后进行遍历；
2. 如果不满足1中所述，那么我们考虑整个数字本来应该存在的位置m, 如果 m 位置上已经存在了数 m, 那么就可以确定数字 m 就是重复的数字，否则转3
3. 如果不满足1, 2， 那么我们直接将i位置的数字m, 放到理想情况下的位置m上，然后继续进行遍历

上面的过程对应的时间复杂度为 ,空间复杂度为，具体实现过程对应就是 解法二 中的代码。
**

解法一 哈希表思想

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

        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++)
            a[i] = 0;
        for (int i = 0; i < nums.length; i++) {
            if (a[nums[i]] > 0)
                return nums[i];
            else 
                ++a[nums[i]];
        }
        return -1;
    }
}

解法二 优化空间

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

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i) {
                continue;
            }
            else if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            else {
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}

参考

《剑指Offer》