Leetcode---剑指Offer题3---数组中重复的数字 1、介绍 2、题解
目录
剑指Offer-面试题4---二维数组中的查找
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
这题的解法并不难，主要考查和面试官的沟通能力，一定要问面试官需要的时间/空间需求！！！
比如要空间O(1)，就不能用别的数据结构。
比如不能修改源数组。
2、题解
这里使用时间O(n)，空间O(1)的解法。
如果数组值和下标不相同，就交换到相同的下标，如果交换时和要交换的下标值相同，就是有重复的元素了。
public int FindRepeatNumber(int[] nums)
{
if (nums == null || nums.Length<=1)
return -1;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] != i)
{
if (nums[i] == nums[nums[i]])
return nums[i];
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
i--;
}
}
return -1;
}