Leetcode|Leetcode 287. Find the Duplicate Number
【Leetcode|Leetcode 287. Find the Duplicate Number】文章作者：Tyan
博客：noahsnail.com|CSDN|
1. Description 
文章图片
Find the Duplicate Number 2. Solution
- Version 1
class Solution {
public:
int findDuplicate(vector& 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& 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& 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;
}
};
Reference
- https://leetcode.com/problems/find-the-duplicate-number/description/
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 运行报错Cannot|运行报错Cannot find module '@babel/compat-data/corejs3-shipped-proposals’
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路