本文主要是介绍LeetCode287. Find the Duplicate Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Constraints:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.
Follow up:
How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?
二、题解
class Solution {
public:int findDuplicate(vector<int>& nums) {if(nums.size() == 1) return -1;int slow = nums[0],fast = nums[nums[0]];while(fast != slow){slow = nums[slow];fast = nums[nums[fast]];}fast = 0;while(fast != slow){fast = nums[fast];slow = nums[slow];}return slow;}
};
这篇关于LeetCode287. Find the Duplicate Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
