二分查找
解题思路
n + 1 个整数，放在长度为 n 的数组里，并且数字都在
[1, n]范围内，根据「抽屉原理」（把 10 个苹果放进 9 个抽屉，至少有一个抽屉里至少放 2 个苹果），至少会有 1 个整数是重复的；定义 left、right 两个指针，统计原始数组中 小于等于 mid 索引 的元素的个数 count；
- 如果
count > mid，重复元素就在区间 [left…mid] 里；- 如果
count <= mid，重复元素一定可以在区间 [mid + 1…right] 里找到；
复杂度
时间复杂度：
O(nlogn)，二分法的时间复杂度为O(logn)，在二分法的内部，遍历数组的时间复杂度为O(n)空间复杂度：
O(1)
代码实现
function findDuplicate(nums) {
let len = nums.length;
let left = 1;
let right = len - 1;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
// 根据 nums 数组中 小于等于 mid 索引 的元素的个数来判断 查找范围
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count > mid) {
right = mid; // 下一轮搜索的区间 [left，mid]
} else {
left = mid + 1; // 下一轮搜索的区间 [mid + 1，right]
}
}
return left;
}
快慢指针
解题思路
该题可以转化成「环形链表寻找入口」，可以参考 leetcode🧑💻 142. 环形链表 II；
数组的值可以看成 next 指针的指向；
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(1)
代码实现
var findDuplicate = function (nums) {
let slow = 0;
let fast = 0;
// 找到相遇的点
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 找到环形链表的入口
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1095. 山脉数组中查找目标值
上一篇
评论
