# 题目链接
# 题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
1
2
3
4
5
2
3
4
5
# 解题思路
方法一:由于只需要找出数组中任意一个重复的数字,因此遍历数组,遇到重复的数字即返回。为了判断一个数字是否重复遇到,使用 map 存储已经遇到的数字,如果遇到的一个数字已经在 map 中,则当前的数字是重复数字。
package main
import (
"fmt"
)
func findRepeatNumber(nums []int) int {
m := make(map[int]int)
for _, value := range nums {
if _, ok := m[value]; ok {
// 存在该数值
return value
} else {
// 不存在
m[value] = 1
}
}
return -1
}
func main() {
nums := []int{2, 3, 1, 0, 2, 5, 3}
num := findRepeatNumber(nums)
fmt.Println("重复的一个数字为: ", num)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
执行用时 : 76 ms, 在所有 Go 提交中击败了 7.58% 的用户
内存消耗 : 9.1 MB, 在所有 Go 提交中击败了 100% 的用户
方法二:排序,看前后元素是否相等
package main
import (
"fmt"
"sort"
)
func findRepeatNumber(nums []int) int {
// 对整型切片进行排序
sort.Ints(nums)
// 遍历切片, 与下一个数字重复就返回
for i, numsSize := 0, len(nums); i < numsSize-1; i++ {
if nums[i] == nums[i+1] {
return nums[i]
}
}
return -1
}
func main() {
nums := []int{2, 3, 1, 0, 2, 5, 3}
num := findRepeatNumber(nums)
fmt.Println("重复的一个数字为: ", num)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
执行用时 : 56 ms, 在所有 Go 提交中击败了 22.35% 的用户
内存消耗 : 6.9 MB, 在所有 Go 提交中击败了 100% 的用户
方法三:因为数组长度为 n, 且数字都在 0 ~ n-1 范围内,所以只需要判断下标 i 是否与 nums[i] 相等即可(如果都相等,说明没有重复元素):
- i 与 nums[i] 相等,继续向下扫描
- i 与 nums[i] 不相等,先比较 nums[i] 与 nums[nums[i]] 的值:
- nums[i] 与 nums[nums[i]] 相等,返回 nums[i]
- nums[i] 与 nums[nums[i]] 不相等,交换 nums[i] 与 nums[nums[i]] ,一直重复
package main
import (
"fmt"
)
func findRepeatNumber(nums []int) int {
for i := 0; i < len(nums); i++ {
for i != nums[i] {
if nums[i] == nums[nums[i]] {
return nums[i]
}
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
}
}
return -1
}
func main() {
nums := []int{2, 3, 1, 0, 2, 5, 3}
num := findRepeatNumber(nums)
fmt.Println("重复的一个数字为: ", num)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
执行用时 : 40 ms, 在所有 Go 提交中击败了 95.89% 的用户
内存消耗 : 8.9 MB, 在所有 Go 提交中击败了 23.87% 的用户