公司网站建设的请示/公司网站设计
力扣287题：寻找重复数
题目描述
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
输入输出样例
输入：nums = [1,3,4,2,2]
输出：2
输入：nums = [3,1,3,4,2]
输出：3
进阶
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
解法一：暴力解法
//已知 nums的长度为n+1，其值均在o~n之间，只有一个重复的数
//时间复杂度O(n^2),空间复杂度O(1)int findDuplicate(vector<int>&nums){if(nums.empty()||nums.size()<2){return 0;}int length=nums.size();int left=0,right=1;while(left<length){while(right<length){if(nums[left]==nums[right]){return nums[left];}right++;}left++;right=left+1;}return 0;}
解法二，二分查找
//使用二分查找的方法//因为若为当前值小于target，其小于target的计数一定小于等于当前的值//因为若为当前值大于target，其大于target的计数一定大于等于当前的值//因为若为当前值等于target，其小于等于target的计数一定大于当前target//时间复杂度O(nlogn),空间复杂度 O(1)int findDuplicate2(vector<int>&nums){int length=nums.size();int left=0;int right=length-1;int mid;int count;while(left<right){mid=(left+right)/2;//count计算数组中小于mid的元素，用来动态调整二分查找的范围count=0; for(int num:nums){//包含中含有等于if(num<=mid){count++;}}//利用count动态调整二分查找的范围//因为含有等于，所以当cout>mid中时，便代表target在mid左区间if(count>mid){right=mid;}else{left=mid+1;}}return left;}
解法三，快慢指针
//解法三，使用快慢指针的思想//因为题意中所有值均小于 num.size()，可以用其值和坐标的变换判断是否存在环，并找到环的入口//时间复杂度O(n),空间复杂度O(1)int findDuplicate3(vector<int>&nums){int length=nums.size();int slow=0,fast=0;//移动快慢指针，直到找到第一个环while(true){//相当于 slow=slow->next//fast=fast->next->nexgtslow=nums[slow];fast=nums[nums[fast]];if(fast==slow){break;}}int startPoint=0;//寻找入口的起点while(true){startPoint=nums[startPoint];slow=nums[slow];//第一次相遇的点即为起点if(startPoint==slow){return slow;}}return -1;}