lt.287. 寻找重复数
[案例需求]
[思路分析一, ]
- 挺恶心的一道题, 各种限制, 不准修改数组, 意味着原地哈希不能用了;
- 空间复杂度为 O(1), 意味着使用集合存储遍历过的数字也不能用了;
- 线性时间复杂度 O(n), for循环或者排序也不能用了;
shiiiiiit, 该怎么解这道题呢?
参考方法: 我们在解答这道题目时, 可能会想到用原地哈希解题, 什么是原地哈希呢? 就是说, 用数组的索引去映射index值, 比如nums[2] = 2, 即index =2的位置上的元素值为2;但是这可恶的题目不允许修改数组, 我们可以把这种映射的关系转移到在链表中寻找环(呜呜呜, 我反正是想不到);
[代码实现]
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
}
[思路分析二, 二分查找]
