03. 数组中重复的数字.md

解题思路

1. 哈希

将数放入哈希表，如果当前哈希表已经有值，说明这个数重复了

// 哈希
func findRepeatNumber(nums []int) int {
    m := make(map[int]struct{})
    for _, v := range nums {
        if _, ok := m[v]; ok {
            return v
        }
        m[v] = struct{}{}
    }
    return -1
}

2. 排序

先把数组排序，相同的肯定排在了一起，比较前后两个数是否相等

// 排序，相同的排在了一起
func findRepeatNumber(nums []int) int {
    sort.Ints(nums)
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            return nums[i]
        }
    }
    return -1
}

3. 利用性质

长度为 n 的数组 nums 里的数字都在范围 0 ~ n-1 内，尝试把当前的数归位到和下标一致，即让 nums[i] = i，所以有三个数：

1. 当前下标 i
2. 当前下标的值 nums[i]
3. 当前下标的值应该被放的位置 nums[nums[i]]

/* 利用性质，让 nums[i] 回到 i 位置
  1. 比较 nums[i] 与 i 的关系，只有不等时才需要回归原位
  2. 比较 nums[i] 与 nums[nums[i]]
  [2, 3, 1, 0, 2, 5, 3]
   1, 3, 2, 0, 2  5  3
   3  1  2  0  2  5  3
   0  1  2  3  2  5  3
   0  1  2  3  2  2回不去了
*/

func findRepeatNumber(nums []int) int {
    for i := range nums {
        // i -> 0
        // nums[0] -> 2
        // nums[nums[0]] -> 1
        for nums[i] != i {
            // 本该回归的位置已经有数回归了，说明重复了
            if nums[nums[i]] == nums[i] {
                return nums[i]
            }
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        }
    }
    return -1
}