剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

哈希表

1
2
3
4
5
6
7
8
9
10
func findRepeatNumber(nums []int) int {
    m := make(map[int]bool)
    for _, n := range nums {
        if _, ok := m[n]; ok {
            return n
        }
        m[n] = true
    }
    return -1
}

原地交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); {
        n := nums[i]
        if n == i {
            i++
            continue
        }
        if n == nums[n] {
            return n
        }
        nums[n], nums[i] = nums[i], nums[n]
    }
    return -1
}