剑指 Offer 03. 数组中重复的数字
剑指 Offer 03. 数组中重复的数字
SakuraTears
发布于 2022-01-13 15:11:19
发布于 2022-01-13 15:11:19
题目
0.png
思路
1.sort后遍历找到一样的返回。时间复杂O(nlogn)。
2.用哈希表遍历如果这个数字为key的value为0则+1，不为0直接return。时间复杂度O(n)，空间复杂度O(n)。
3.时间复杂度O(n)，空间复杂度为O(1)的方法：
题目写出数组范围为0~n-1，所以当数组排序之后i的位置的数字应该为i，由于数组中有重复的数字，所以有的位置没有数字，有的位置有多个数字。
从头到尾重新遍历这个数组，当nums[i] != i时，比较nums[nums[i]]位置的值，如果相同则直接return，不同则把两个数交换位置，重复以上过程直到nums[i] == i，或者return。
func findRepeatNumber(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
if i != nums[i] {
if nums[i] == nums[nums[i]] {
return nums[i]
} else {
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
i--
}
}
}
return -1
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年01月04日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
