题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
思路参考的是CYC大神,降低一下复杂度,因为题里面数组的元素在[0,n-1]的范围里面 那么我们可以借助数组的索引来找重复,先把i和nums[i]进行交换 如果有重复的话进行判断
public int duplicate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
swap(nums, i, nums[i]);
}
swap(nums, i, nums[i]);
}
return -1;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}