3 数组中重复的数字

牛客

描述

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

示例：

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

返回值：2或3都是对的

---

可以先将数组排序，时间复杂度 O(nlogn)，时间复杂度过高，而且由于只需要返回一个重复数字，没有必要对整个数组排序。

也可以用辅组数组或者 hash 表来实现。时间复杂度 O(n) ，空间复杂度 O(n)，

public int duplicate (int[] numbers) {
    boolean[] arr=new boolean[numbers.length];
    for(int i:numbers){
        if(arr[i]==false)
            arr[i]=true;
        else
            return i;
    }
    return -1;
}

如果允许修改原有的数组，可以有空间复杂度 O(1) 的办法。从第一个数字开始遍历数组，将数字与相应的下标上的数字比较，如果一样则返回这个数字，如果不一样，将数字与相应下标的数字交换，再将新的数字与相应下标的数字交换，直到所有数字都到数字的对应下标。

import java.util.*;
public class Solution {
    public int duplicate (int[] numbers) {
        int cur,t;
        for(int i=0;i<numbers.length;++i){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    return numbers[i];
                } else {
                    t=numbers[numbers[i]];
                    numbers[numbers[i]]=numbers[i];
                    numbers[i]=t;
                }
            }
        }
        return -1;
    }
}