数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解法一：

通过排序将数组排序，遍历数组便可以得到第一个重复的数字，快排的事件复杂度为O（nlogn）。

解法二：

可以通过Set、Map、数组等作为辅助空间，遍历输入序列时记录其出现的次数，第一个次数为2的便为所求的数字。（使用数组作为辅助空间时，由于序列中数字取值为0到n-1，所以可以使用a[i]记录i）。事件复杂度为O（n），空间复杂度为O（n）。

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length == 0) {
            duplication[0] = -1;
            return false;
        }
        Set<Integer> set = new HashSet<Integer>();
        for(int i : numbers) {
            if(set.contains(i)) {
                duplication[0] = i;
                return true;
            }
            else
                set.add(i);
        }
        duplication[0] = -1;
        return false;
    }
}

解法三：

虽然该算法可以实现时间复杂度为O（n），空间复杂度为O（1）。但是只适合较小的数字，很容易产生溢出，因此极度不推荐，仅作为一种思路记录下来。
令m = numbers[i],将numbers[m]置为 m + length, 这样表示已经存在m，假设以后遍历到 n = numbers[j], 若此时numbers[n]已经被加了lenth，可以得到之前已经存在过了n，则n便是第一次重复的数字。

这种算法修改了输入数据，并且在+length的过程中很容易导致溢出。

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length == 0) {
            duplication[0] = -1;
            return false;
        }
        for(int i = 0; i < length; i++) {
            int m = numbers[i];
            if(m >= length)
                m -= length;
            if(numbers[m] > length) {
                duplication[0] = m;
                return true;
            }
            numbers[m] += length;
        }
        duplication[0] = -1;
        return false;
    }
}

如果将题意修改为输出任意一个重复数字即可，不要求输出第一个重复数字。
由于输入序列中数字取值为0到n-1，若数组中没有重复数字，则numbers[i]中的值一定为i。
我们可以利用这一特性，从头遍历输入序列，将i放到numbers[i]上，若此时numbers[i]上早就存在了数字i，则i就是一个重复的数字。
即：
从头遍历输入序列，令j = numbers[i]。
若j = i，则i++；
若j！= i，则判断numbers[j] 是否等于j。若numbers[j] = j，则j即为一个重复的数字；
若numbers[j] != j，则交换numbers[i]与numbers[j]。继续判断当前i。

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int i = 0, j = 0;
        if(numbers == null || length == 0) {
            duplication[0] = -1;
            return false;
        }
        while(i < length) {
            if(numbers[i] != i) {
                j = numbers[i];
                if(numbers[j] == numbers[i]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                else {
                    int tmp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = tmp;
                }
            }
            else
                i++;
        }
        duplication[0] = -1;
        return false;
    }
}