题目要求
数组中一共有n个数字,所有数字的范围都在$0 \sim n - 1$之间,所以$0 \sim n - 1$中的 每个数字都会出现,并且只会出现一次,否则就是有重复的;
举例:$n = 5$,那么$0,1,2,3,4$ 都会出现一次;
那么就可以直接想到用Arrays进行数组排序,然后判断nums[i] == nums[i + 1]
就可以了,等于说明有重复的,但是时间复杂度就是O(nlogN)
,所以采用了另一种方法
算法
思想:把每个数放到对应的位置上,即i == nums[i]
,如果不相等就交换位置,也就是0位置将会存储0, i位置将会存储i
步骤
- 先把某些数字不在$0 \sim n - 1$范围内处理了,直接返回-1就好了
- 如果
nums[i] != nums[nums[i]]
那么就交换位置,直到放到正确的位置上 - 如果
i != nums[i]
,说明出现了重复的数字,返回nums[i]
即可
时间复杂度分析
每次swap
操作都会将一个数放在正确的位置上,最后一次$swap$会将两个数同时放到正确位置上,一共只有 $n$ 个数和 $n$ 个位置,所以swap
最多会进行 $n−1$ 次。所以总时间复杂度是 $O(n)$。
问题
问题1:为什么不会出现死循环
当出现重复的数字时,$nums[0] = 2,nums[nums[0]] = nums[2] = 2, 2 == 2$,即$nums[i] == nums[nums[i]]$,就会跳出循环,所以不会出现死循环
也就是说如果出现了重复的数字,最后一次swap操作一定是重复的数字进行比较,进而跳出循环,但是$i != nums[i]$,所以返回$nums[i]$即可
第一种方法代码
class Solution {
public int duplicateInArray(int[] nums) {
int n = nums.length;
for(int x : nums)
if(x < 0 || x >= n) return -1;
Arrays.sort(nums);
for(int i = 0; i < n - 1; i ++)
{
if(nums[i] == nums[i + 1]) return nums[i];
}
return -1;
}
}
Java代码
class Solution {
public int duplicateInArray(int[] nums) {
int n = nums.length;
for(int i = 0; i < n; i ++ )
if(nums[i] < 0 || nums[i] >= n) return -1;
for(int i = 0; i < n; i ++ )
{
while(nums[i] != nums[nums[i]])
{
int t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
if(i != nums[i]) return nums[i];
}
return -1;
}
}