题目

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

题解

思路一（hash表）

遍历数组的每个元素num，检查hash表中是否存在

• hash表中存在，则直接返回
• hash表中不存在，则写入hash表

思路二（原地交换）

数组nums长度为n，所有元素都在0~n-1之间，可以通过交换，使得元素的索引和元素的值一一对应，从而实现hash的功能

• 从索引i = 0开始遍历数组
• 如果i == nums[i]，说明元素的值和索引已经对应，无需交换，跳过
• 如果nums[i] == nums[nums[i]]，说明索引i和nums[i]对应的元素的值相同，即找到重复值，返回nums[i]
• 否则，交换索引i和nums[i]值

代码

hash表

func findRepeatNumber(nums []int) int {
	hash := make(map[int]struct{})
	for _, v := range nums {
		if _, ok := hash[v]; ok {
			return v
		} else {
			hash[v] = struct{}{}
		}
	}
	return -1
}

原地交换

func findRepeatNumber2(nums []int) int {
	for i := 0; i < len(nums); {
		if nums[i] == i {
			i++
			continue
		}
		if nums[i] == nums[nums[i]] {
			return nums[i]
		}
		nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
		fmt.Println(nums)
	}
	return -1
}