【LeetCode】剑指 Offer ＜二刷＞（1）

目录

前言：

题目：剑指 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
}

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~