剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 思路哈希表法： 由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。
时间复杂度：遍历数组O(n)，查询hash表为O(1)，整体还是为O(n)
空间复杂度：需要开辟一个数组暂存遍历的数值，所以为O(n)
func findRepeatNumber(nums []int) int { if nums == nil || len(nums)==0 { return -1 } mp := map[int]int{} for i,v := range nums{ if _,ok := mp[v];ok { //如果hash表中存在，表明出现了重复数值 return v } mp[v] = i } return -1 }原地置换法:如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿下标m对应的值与下标m对应的值作为下标的值交换，即nums[m]与nums[nums[m]]交换。在交换过程中，如果有重复的数字发生，那么终止返回ture
时间复杂度还是O(n)
降低了空间复杂度，使空间复杂度从O(n) ——>O(1)
func findRepeatNumber(nums []int) int { if nums == nil || len(nums)==0 { return -1 } for i:=0;i<len(nums);i++{ //下标与对应值不等 if i!=nums[i]{ if nums[i]==nums[nums[i]]{ //说明找到了重复的值 return nums[i] } } //交换 nums[i],nums[nums[i]] = nums[nums[i]],nums[i] } return -1 }