剑指offer系列——找出数组中重复的数字

题目描述：

找出数组中重复的数字。


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

示例 1：

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


链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

思路：

题目没有限制空间和事件。

方法一：利用IndexOf查找当前数组中有无相同字符串，
来查找重复元素。时间复杂度O（N）,空间复杂度O（N）。

方法二：哈希表：将数组中的值变为对象属性，
如果这个值存在，对应属性值为true。这个在时间上会比方法一快一些。

方法三：原地哈希：不如让我原地升天好了。这个方法是基于这句话：“在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内”的。将从头开始遍历，将每个值放到与之对应的下标上去，。比如数组nums是[2,2,1]。num[0]是2，就将num[2]的1和num[0]的2换位
置，就是[1,2,2]。再检测当前num[0]上的数是否放在了对的下标上，
当然是没有啦。我们将num[0]的1和num[1]的2换位置就变成[2,1,2]，再看num[0]现在是否放对了位置？没对就继续换，发现num[2]的数值已经是2了，所以2就重复了。

这种方式无需开辟出新空间，节省了空间，但是思想不是很好理解。

代码：

方法一：
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
let tmp=[];
	for(let v of nums){
		if(tmp.indexOf(v)!==-1){
			return v;
		}else{
			tmp.push(v);
		}
	}
	return false;
};

方法二：
var findRepeatNumber = function(nums) {
let tmp={};
	for(let v of nums){
		if(tmp[v]){
			return v;
		}else{
			tmp[v]=true;
		}
	}
	return false;
};

var findRepeatNumber = function(nums) {
    let length = nums.length;
    for (let i = 0; i < length; ++i) {
        while ((num = nums[i]) !== i) {
            if (num === nums[num]) {
                return num;
            }
            [nums[i], nums[num]] = [nums[num], nums[i]];
        }
    }
};

喵啊：

哈希表的方法很简单，好理解。
原地哈希在限制空间时可以考虑。

有不对的地方欢迎指正呀

剑指offer系列——找出数组中重复的数字

推荐阅读