描述

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

示例

输入：

[2,3,1,0,2,5,3]

返回值：

2

说明：

2或3都是对的 

解题思路

1.暴力

2.位置重排

数组长度为 n 只包含了 0 到 n−1 的数字，那么如果数字没有重复，这些数字排序后将会与其下标一一对应。那我们就可以考虑遍历数组，每次检查数字与下标是不是一致的，一致的说明它在属于它的位置上，不一致我们就将其交换到该数字作为下标的位置上，如果交换过程中，那个位置已经出现了等于它下标的数字，那肯定就重复了。

代码实现

暴力：

/**
 * 【暴力】数组中重复的数字
 *
 * @param numbers int 整型一维数组
 * @return int 整型
 */
func duplicate(numbers []int) int {
    // 遍历数组
    for i := 0; i < len(numbers)-1; i++ {
        for j := i + 1; j < len(numbers); j++ {
            if numbers[i] == numbers[j] {
                return numbers[i]
            }
        }
    }
    return -1
}

位置重排：

/**
 * 位置重排
 *
 * @param numbers int 整型一维数组
 * @return int 整型
 */
func duplicate2(numbers []int) int {
    for i := 0; i < len(numbers); i++ {
        if numbers[i] != i {
            // 当前值对应的下标已经有正确的对应数值，说明重复
            if numbers[i] == numbers[numbers[i]] {
                return numbers[i]
            }
            // 未存在，则交换位置
            numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
        }
    }
    return -1
}