【LeetCode】剑指 Offer ＜二刷＞（1）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】剑指 Offer ＜二刷＞（1）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

题目：剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

前言：

刚学 golang 半个多月，看了一堆的文档啊，框架啊，许许多多的东西，学到了很多，但是代码没有怎么上手写，所以我就决定用 golang 二刷剑指 Offer，增强我 golang 的代码能力。

题目：剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）

【LeetCode】剑指 Offer ＜二刷＞（1）,38 天二刷剑指 Offer,golang,算法

题目的接口：

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
}