文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Find the Duplicate Number
2. Solution
- Version 1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if((nums[i] ^ nums[j]) == 0) {
return nums[i];
}
}
}
}
};
- Version 2
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int i = 0;
int j = 0;
while(true) {
i = nums[i];
j = nums[nums[j]];
if(i == j) {
break;
}
}
i = 0;
while(true) {
i = nums[i];
j = nums[j];
if(i == j) {
return i;
}
}
}
};
- Version 3
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 1;
int high = nums.size() - 1;
while(low < high) {
int mid = (low + high) / 2;
int count = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] <= mid) {
count++;
}
}
if(count <= mid) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
};
