LeetCode287 寻找重复数

链接: https://leetcode-cn.com/problems/find-the-duplicate-number/

题面

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。

解法

有多种解法,包括二分,交换,快慢指针

代码

二分解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size();
while(l < r) {
int mid = (l + r) / 2, cnt = 0;
for (int n: nums) {
if (n <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
};

交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
// vector<int> g(n + 1);
while(1) {
for (int i = 0; i < n; i++) {
if (nums[i] == i + 1) {
continue;
}
if (nums[i] == nums[nums[i] - 1]) return nums[i];
swap(nums[i], nums[nums[i] - 1]);
}
}
return 0;
}
};

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[fast];
fast = nums[fast];
} while(fast != slow);
slow = 0;
while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};