网站建设 中国移动,网站高端建设,ps网页设计步骤及方法,网站架构优化目录
前言#xff1a;
题目#xff1a;剑指 Offer 03. 数组中重复的数字 - 力扣#xff08;LeetCode#xff09;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
写在最后#xff1a; 前言#xff1a; …目录
前言
题目剑指 Offer 03. 数组中重复的数字 - 力扣LeetCode
题目的接口
解题思路
代码
过啦
写在最后 前言
刚学 golang 半个多月看了一堆的文档啊框架啊许许多多的东西学到了很多但是代码没有怎么上手写所以我就决定用 golang 二刷剑指 Offer增强我 golang 的代码能力。
题目剑指 Offer 03. 数组中重复的数字 - 力扣LeetCode
题目的接口 func findRepeatNumber(nums []int) int {} 解题思路
这道题目一上来我就能想到两个比较常见的解法首先是暴力解法就是从第一元素开始遍历直到遍历到另一个一样的元素就停下这种解法是 O(N^2)复杂度非常的差就不考虑了
第二种方法是用哈希表把数据依次放进哈希表中等再次遇到同样的元素就找到了这个的复杂度是 O(N)但是这种方法会有额外的空间开销我就直接实现一下
func findRepeatNumber(nums []int) int {hash : make([]int, len(nums))for _, n : range nums {if hash[n] 1 {return n} else {hash[n] 1}}return -1
}
虽然是二刷剑指 Offer但是我还是忘了最优解看了眼别的大佬的解答第三种方式是基于题目要求的解法题目限定了数组中的值是 0 ~ n - 1具体思路就是遍历数组将数组的值作为索引把该索引位置的值改成负数如果我们遍历到负数就先获取他变负数前的值在根据这个值作为索引如果索引位置是负数证明这个值重复出现。
如果看一遍看不懂没关系对着代码画个图模拟一下就很清晰了以题目的示例为例
示例 1
输入
[2, 3, 1, 0, 2, 5, 3]
输出2 或 3
遍历数组第一个值是 2他的索引位置是 1 0我们通过先取相反数再减一的方式将索引 2 位置的值变成负数执行完数组的第一个值后[ 2, 3, -2, 0, 2, 5, 3 ]
第二个值是 3他的索引位置是 0 0同样的做法[ 2, 3, -2, -1, 2, 5, 3 ]
第三个值是 1他的索引位置是 3 0同样的做法[ 2, -4, -2, -1, 2, 5, 3 ]
第四个值是 0他的索引位置是 2 0同样的做法[ -3, -4, -2, -1, 2, 5, 3 ]
第五个值是 2他的索引位置是 -2 0是负数我们就得出值了。
这里补充一点如果我们取到的值就是负数该怎么办加一再取相反数就能获得他原本的索引值
代码
func findRepeatNumber(nums []int) int {for _, n : range nums {if n 0 { // 获取原本的索引值n -(n 1)}if nums[n] 0 { // 如果是负数证明找到了return n} else { // 将该位置设置成负数nums[n] -nums[n] - 1}}return -1
}
过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
