如何查找数组中重复的数字

题目

在一个长度为 n 的数组里，所有数字都在 0~n-1 的范围内。只知道某些元素是重复的，但不知道重复了几次，也不知道有几个是重复的。如何找出数组中任意重复的数字？

解法

常规

常规方法就是遍历数组，将遍历到的元素存储到一个 map/set 中，边遍历边将元素与 map/set 比较 ，如果存在，则是重复元素。时间复杂度 O(n)，空间复杂度 O(n)。

func getDuplicatedNumber(data []int) (bool, int) {
	if len(data) == 0 {
		return false, 0
	}
	elements := make(map[int]int)

	for _, n := range data {
		if n > len(data)-1 {
			return false, 0
		}
		if cnt, ok := elements[n]; ok {
			if cnt < 2 {
				// 第一次重复
				return true, n
			}
		} else {
			elements[n] = 1
		}
	}
	return false, 0
}


func main() {
	var s1 = []int{1, 3, 2, 5, 2, 6, 7, 3, 2}
	fmt.Println("原始数组：", s1)
	duplicated, data := getDuplicatedNumber(s1)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s2 = []int{1, 3, 2, 5, 6, 0, 4}
	fmt.Println("原始数组：", s2)
	duplicated, data = getDuplicatedNumber(s2)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s3 []int
	fmt.Println("原始数组：", s3)
	duplicated, data = getDuplicatedNumber(s3)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s4 = []int{1, 3, 2, 100}
	fmt.Println("原始数组：", s4)
	duplicated, data = getDuplicatedNumber(s4)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}
}

输出：

原始数组： [1 3 2 5 2 6 7 3 2]
存在重复元素： 2
原始数组： [1 3 2 5 6 0 4]
不存在重复元素
原始数组： []
不存在重复元素
原始数组： [1 3 2 100]
不存在重复元素

交换元素

上面常规的方法，思路清晰和简单，但效率还有可以提升的空间。

如果排好序并将 n 放到位置 n 后，有的位置会为空，有的位置会有重复的元素，那么我们可以这样找出重复的元素：

func getDuplicatedNumber(data []int) (bool, int) {
	if len(data) == 0 {
		return false, 0
	}
	for _, n := range data {
		if n > len(data)-1 {
			// 不满足题目要求
			return false, 0
		}
	}
	for idx := range data {
		for idx != data[idx] {
			if data[idx] == data[data[idx]] {
				// 出现重复元素
				return true, data[idx]
			} else {
				// 交换数据
				data[idx], data[data[idx]] = data[data[idx]], data[idx]
			}
		}
	}
	return false, 0
}

func main() {
	var s1 = []int{1, 3, 2, 5, 2, 6, 7, 3, 2}
	fmt.Println("原始数组：", s1)
	duplicated, data := getDuplicatedNumber(s1)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s2 = []int{1, 3, 2, 5, 6, 0, 4}
	fmt.Println("原始数组：", s2)
	duplicated, data = getDuplicatedNumber(s2)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s3 []int
	fmt.Println("原始数组：", s3)
	duplicated, data = getDuplicatedNumber(s3)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}

	var s4 = []int{1, 3, 2, 100}
	fmt.Println("原始数组：", s4)
	duplicated, data = getDuplicatedNumber(s4)
	if duplicated {
		fmt.Println("存在重复元素：", data)
	} else {
		fmt.Println("不存在重复元素")
	}
}

输出：

原始数组： [1 3 2 5 2 6 7 3 2]
存在重复元素： 3
原始数组： [1 3 2 5 6 0 4]
不存在重复元素
原始数组： []
不存在重复元素
原始数组： [1 3 2 100]
不存在重复元素

这个解法时间复杂度 O(n)，空间复杂度 O(1)。