题目:找出数组中反复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范畴内。数组中某些数字是反复的,但不晓得有几个数字反复了,也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。

链接: 力扣Leetcode—剑指Offer—数组—03.数组中反复的数字.

示例 1:

输出:[2, 3, 1, 0, 2, 5, 3]
输入:2 或 3

思路:一开始用两个 for 循环遍历,一下子就超时了,代码如下:

func findRepeatNumber(nums []int) int {    n := len(nums)    res := 0    for i := 0; i < n; i++ {        for j := i + 1; j < n; j++ {            if nums[i] == nums[j] {                res = nums[i]                break            } else {                continue            }        }    }    return res}

简简单单超时:


前面遍历一下数组,用哈希表存储数字呈现的次数,如果 >1 ,就输入那个 key 并跳出循环

Go代码如下:

package mainimport "fmt"func findRepeatNumber(nums []int) int {    m := make(map[int]int)    res := 0    for _, v := range nums {        m[v]++    }    for key, v := range m {        if v > 1 {            res = key            break        } else {            continue        }    }    return res}func main() {    a := []int{3, 4, 2, 0, 0, 1}    fmt.Println(findRepeatNumber(a))}

提交截图