剑指 Offer 03. 数组中重复的数字
剑指 Offer 03. 数组中重复的数字
Zoctopus
发布于 2022-05-10 20:54:14
发布于 2022-05-10 20:54:14
今天开始争取每天更新至少一道《剑指offer》的题解
题目
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000题解
难度为简单。
解法一：循环+Map
一次遍历，将扫描到数字做判断，如果可以在map中查到，就添加进去，否则返回这个数字，因为这个数字已经在map里存在了，属于重复数字。
//Go
func findRepeatNumber(nums []int) int {
var nummap = make(map[int]bool)
for _,num := range nums {
if !nummap[num] {
nummap[num] = true //map中没有这个num
} else {
return num //重复，直接返回
}
}
return -1
}leetcode-cn执行：
执行用时：
56 ms, 在所有 Go 提交中击败了8.84%的用户
内存消耗：8.9 MB, 在所有 Go 提交中击败了39.48%的用户牛客网执行：
运行时间：3ms
超过100.00%用Go提交的代码
占用内存：832KB
超过100.00%用Go提交的代码解法二：原地交换
遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = inums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。可以看这个题解
//Go
func findRepeatNumber(nums []int) int {
i := 0
for i < len(nums) {
if nums[i] == i {
i++
continue
}
if nums[nums[i]] == nums[i] {
return nums[i]
}
tmp := nums[i]
nums[i] = nums[tmp]
nums[tmp] = tmp
}
return -1
}leetcode-cn执行：
执行用时：
40 ms, 在所有 Go 提交中击败了86.59%的用户
内存消耗：8.7 MB, 在所有 Go 提交中击败了89.50%的用户本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录