一刷 07/2022
Version #1 Detect the cycle
Proof
L = y + z = the length of the cycle
-- x -->----y----->|
|---- z------|
What we want to prove is that x % L = z -> means if x is much longer than L we just want to take the remaining part after subtracting multiple Ls
Given slow pointer goes (x + y), fast pointer gose x + N(y + z), and fast pointer is 2 times faster than slow pointer
When they meet at the meeting point, the slow pointer only walks (x + y) distances instead of (x + y) + kL. That's because that if the slow pointer walks the full cycle, then the fast pointer has walked 2 times of the full cycle, and it must has caught up the slower pointer more than once
2 (x + y) = x + y + kL
x + y = kL
x = kL - y = (k - 1)L + y + z - y = (k - 1)L + z
x % L = z
Time O(N)
Space O(1)
class Solution {
public int findDuplicate(int[] nums) {
// It doesn't matter if there's any stand alone cycles e.g. [2, 1, 2] -> index 1 points to element 1, because we never have chance to get into them
// Since there's no number 0, index 0 will never points back to itself
// If there's duplicate number, then there have multiple index pointing to the same next index and forms a cycle
// 0 -> 2 <->
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// now slow == fast
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
}
Version #2 Binary Search
Time O(NlogN)
Space O(1)
class Solution {
public int findDuplicate(int[] nums) {
// binary search
int start = 1, end = nums.length - 1;
// If there's no duplicates smaller than number a, then there's exactly a numbers smaller than or equals to a
while (start < end) {
int mid = start + (end - start) / 2;
int cnt = countSmallerOrEqual(nums, mid);
if (cnt <= mid) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
private int countSmallerOrEqual(int[] nums, int a) {
int cnt = 0;
for (int num : nums) {
if (num <= a) {
cnt++;
}
}
return cnt;
}
}
No comments:
Post a Comment