剑指Offer面试题 3 ：数组中重复的数字

题目

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

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

思路：

题目中的关键信息：

1. 由于这个数组的长度为 n，而且里面所有的数字都在 0 到 n-1 的范围内。
2. 只要求找出数组中任意一个重复的数字。

解法

我们有三种解法可以选择：

1. 给数组进行排序，最好的时间复杂度就是O(nlogn)。
2. 使用一个hashmap，只需要遍历一次添加到hashmap中，再以O(1)的时间复杂度拿到重复的数字。该算法时间复杂度为O(n)，空间复杂度为：O(n)。
3. 使用题目中给出的关键信息来做（原因：由于所有的数子都在0 到 n-1 范围内，也就是该数组中所有的数字都能用数组的下标来进行表示 ），让数组中每一个数字都放在和该数字相等的数组下标。时间复杂度为O(n)，空间复杂度为O(1)。
   例如：

// 扫描数组，并把对应的数字和该数字相等的数组下标位置的数字进行交换。
{2,3,0,1,4,3} // 数组下标0，数字2，和数组下标为2的数字（0），判断不相等，则进行交换，否则直接返回该数字。
{0,3,2,1,4,3} // 数组下标0，数字0，相等。扫描下一个数，下一个数数组下标1，数字3，和数组下标为3的数字 (4) 进行判断，不相等则交换。
{0,4,2,1,3,3} // 数组下标还是为1，数字4，和数组下标4的数字 (3) 进行判断，不相等则交换
{0,3,2,1,3,4} // 数组下标还是1，数字3，和数组下标3的数字（3）进行判断，相等，直接返回该数字。

代码

public class solution{
  public int duplicate(int[] nums){
        // 这里可以问一下面试官，要直接抛出异常还是返回 -1 
        if(nums == null || nums.length <= 0){
            return -1;
        }
        for(int i = 0;i <nums.length;i++){
            //这里要使用while
            while(nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                swap(nums,i,nums[i]);
            }
        }
        return -1;
    }
    private void swap(int[] nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}