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

分析

假如数组为 {2, 3, 1, 0, 2, 5}，则输出为 2。如果要求不能使用排序，也不能使用额外的标记，我们可以利用 所有数字都在 0 到 n-1 的范围内 这一特点。从头到尾依次扫描数组中的数字，将值为 i 的元素调整到数组索引为 i 的位置。

首先，数组索引为 0 的元素是 2，而索引位置为 2 的元素是 1，由于不相等，所以交换位置，交换后的数组为 {1, 3, 2, 0, 2, 5}；接着数组索引为 0 的元素是 1，而索引位置为 1 的元素是 3，再交换位置，交换后的数组为 {3, 1, 2, 0, 2, 5}；再看数组索引为 0 的元素是 3，而索引位置为 3 的元素是 0，由于不相等，再交换位置，交换后的数组为 {0, 1, 2, 3, 2, 5}，此时 {0, 1, 2, 3} 都已经排好位置了。再遍历到第四个元素 3 时，由于索引位置为 2 的元素已经是 2 了，所以就找到了一个重复的元素。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public boolean duplicate(int[] nums, int length, int[] duplicate){
    if(nums == null || length <= 0) return false;
    for (int i = 0; i < length; i++) {
        if(nums[i] < 0 || nums[i] > length - 1) return false;
    }
    for (int i = 0; i < length; i++) {
        while(nums[i] != i){
            if(nums[i] == nums[nums[i]]){
                duplicate[0] = nums[i];
                return true;
            }
            // 交换 nums[i] 和 nums[nums[i]] 的位置
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return false;
}

详解

第 2~5 行进行边界检查。第 6 行开始遍历数组中的元素，其中 while 循环只要第 i 元素和 i 不相等，就交换位置。但是第 8 行，如果发现原来的位置已经有对应的元素了，那么就返回重复的元素。