剑指offer-在一维数组中找重复出现的数。

描述:

数组大小为n，数字都是0-n-1，找数组中重复出现的数。

思路：

1.用哈希表记录数字是否出现过，需要额外空间。
2. 每个数都在0-n-1间。对数组排序，每个数应该在的下标与它本身的数相同，每个数经历最多两次交换到达应该在的下标。若发现此时位置上有和它一样的数就说明它是重复的。
不用额外空间。

代码：

bool FindduplicateInN(int arr[], int len, int& num)
{
	if (arr == NULL || len <= 0)
		return false;
	for (int i = 0; i < len; i++)
	{
		if (arr[i] >= len)
			return false;
	}
	for (int i = 0; i < len; i++)
	{
		
		while (arr[i] != i)
		{
			int j = arr[i];
			if (arr[j] == arr[i])
			{
				num = arr[j];
				return true;
			}
			else
			{
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}

		}
	}
	return false;
}