AcWing 13. 找出数组中重复的数字
原题链接
简单
作者:
分子
,
2021-01-22 17:10:20
,
所有人可见
,
阅读 4
//原地置换
//将每个元素放到正确的位置,比如0放到nums[0] ,i--nums[i]
//如果 nums[i] != nums[nums[i]] ,就交换元素,放到正确的位置
//如果nums[i] == nums[nums[i]] && nums[i] != i,说明该位置的元素就是重复的元素,返回重复元素
//时间复杂度 O(n)
//空间复杂度 O(1)
class Solution {
public int findRepeatNumber(int[] nums) {
int n = nums.length;
for(int i : nums) {
//判断元素范围
if(i<0 || i>n-1) {
return -1;
}
}
for(int i = 0;i < n;i++) {
while(nums[i] != nums[nums[i]]) {
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
if(nums[i] != i) {
return nums[i];
}
}
return -1;
}
}