Find the Duplicate Number
LeetCode https://leetcode.cn/problems/find-the-duplicate-number/
Binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
int l = 1, r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
return ans;
}
}
Complexity
- Time = O(logn)
- Space = O(1)
Two pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}
slow = 0;
while (true) {
slow = nums[slow];
fast = nums[fast];
if (slow == fast) {
break;
}
}
return slow;
}
}
Complexity
- Time = O(n)
- Space = O(1)
This post is licensed under CC BY 4.0 by the author.