找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法1:原地交换,使得数组中的数与下标一一对应,若交换前已经对应,则为重复
func findRepeatNumber(nums []int) int { for i:=0;i<len(nums);i++{ for nums[i]!=i{ //注意这里一定不能将for改为if if nums[nums[i]]==nums[i]{ return nums[i] //返回重复元素 } nums[i],nums[nums[i]]=nums[nums[i]],nums[i] //不等就交换 } } return 1 }
解法2:哈希 map
func findRepeatNumber(nums []int) int{ var res int numap:=make(map[int]int) for i:=range nums{ if _,ok:=numap[nums[i]]; ok{ //固定语法,如果map里有以该元素为key的键值对,则ok为true,即找到重复元素,未找到ok为false,在map中加上该键值对 res=nums[i] //ok为true,找到重复元素,直接退出循环 break } numap[nums[i]]++ } return res }