6.15数组中重复数字 - WisperDin/blog GitHub Wiki

描述

面试题3（一）：找出数组中重复的数字 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了， 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}， 那么对应的输出是重复的数字2或者3。

思路

由于**数据的范围仅限于0 - n-1 **，并且要求输出一个重复的即可，可以扫描数组，将每个元素交换至其value对应的数组位置中，每次交换前查看要交换的位置里面的值与交换值是否相同，相同则出现重复 通过此法实现 时间复杂度O(N) 空间复杂度O(1)

实现

func DuplicationInArray(arr []int)(int,bool){
	if len(arr)<=0 {
		return -1,false
	}

	for i:=0;i<len(arr)-1;i++ {
		for	arr[i] != i {
			//the place want to swap contain value
			if arr[i] == arr[arr[i]] {
				return arr[i],true
			}
			arr[i],arr[arr[i]] = arr[arr[i]],arr[i]
		}
	}
	return -2,false
}

总结

注意题目中比较特别的条件限制，往往是算法实现的关键前提