寻找重复数字 0~N-1 个数字
长度为n+1，所有的数字在1~n的范围内，所以至少有一个数字是重复的。请找出任意一个重复的数字，但不能修改输入的数字。例如[2,3,5,4,3,2,6,7]那么对应的输出应该是数字2后者3
思路
- 方法一使用一个n+1的数组，直接把原数组里面的每一个值放到对一个的数组下标里这样很容易知道哪个值是重复的
- 方法二 二分法
代码
方法一 代码
function isRepy(nums) {
const copyNums = [];
for (let i=0; i<nums.length; i++) {
if (copyNums[nums[i]]) {
return nums[i];
}
copyNums[nums[i]] = true;
}
return -1;
}
方法二 代码
function getDuplication(nums, len) {
if (!nums || len <= 0) {
return -1;
}
let start = 1;
let end = len - 1;
while (end >= start) {
let middle = ((end - start) >> 1) + start;
let count = countRange(nums, len, start, middle);
if (end === start) {
if (count > 1) {
return start;
}
break;
}
if (count > (middle - start + 1)) {
end = middle;
} else {
start = middle + 1;
}
}
return -1;
}
function countRange(nums, len, start, end) {
if (!nums) {
return 0;
}
let count = 0;
for (let i=0; i<len; i++) {
if (nums[i] >= start && nums[i] <= end) {
count++;
}
}
return count;
}
复杂度分析
方法一
- 时间复杂度: O(N)
- 空间复杂度: O(N)
方法二
- 时间复杂度: O(NlogN)
- 空间复杂度: O(1)