题目描述
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明:
不能更改原数组(假设数组是只读的)。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字,但它可能不止重复出现一次。
方法1
思路
二分法 思考根据什么条件缩小范围。
因为这道题的时间复杂度要求是小于O(n2),而小于O(n2)复杂度最接近的复杂度是O(nlogn),而对于一个一维数组,寻找满足给定条件的数并且
复杂度中含有logn的算法,我们很容易想到二分查找,使用二分法 我们在区间[l, r]中搜索,首先求出中点mid,然后遍历整个数组(复杂度o(n)),统计所有大于等于l小于等于mid的数的个数,如果个数小于等于mid-l+1,则说明在[mid+1, n]中含有重复值,反之,在[1, mid]中含有重复值,然后依次类推,直到搜索完成。
代码实现1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1;
int r = nums.size()-1;
while(l<=r)
{ //控制节奏,提前终止
if(l==r)
return l;
int mid = l+(r-l)/2;
int cnt = 0;
for(int i = 0;i < nums.size();i++)
{
if(nums[i]>=l && nums[i]<=mid)
cnt++;
}
//对于这个范围缩小的方向转换情况,我们可以使用反证法进行证明
if(cnt<=(mid-l+1))
l = mid+1;
else
r = mid;
}
return -1;
}
};
代码实现2
上面的思路的另一种写法
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1;
int r = nums.size()-1;
//对于查找的过程想明白后,我们可以灵活地设置循环条件及
//退出循环时终止时的状态
while(l<r)
{
int mid = l+(r-l)/2;
int cnt = 0;
for(int i = 0;i < nums.size();i++)
{
if(nums[i]>=l && nums[i]<=mid)
cnt++;
}
//对于这个范围缩小的方向转换情况,我们可以使用反证法进行证明
if(cnt<=(mid-l+1))
l = mid+1;
else
r = mid;
}
return l;//这里的二分查找终止条件为l何r相等,因此这里返回l或者r都行
}
};
方法2
思路
注:这个方法的适用范围要大的多,只要数组元素的值的范围在0-nums.size()-1之内,就可以找出重复的元素。
数组可以看出一个特殊的链表,数组下标为链表节点的地址,数组中元素的值为这个链表节点的next节点的地址(注:这里的链表节点内只有"next指针值",没有"val值"),然后问题可以转化为求链表中环的入口的问题(这个入口有两个元素指向它),可以使用快慢指针解决,如果这个"特殊的链表"发生"自己指向自己"的情况(也就是说形成"单节点环"),例如,1,1,1,1,2,3,此时我们的算法仍能正常的工作,这个算法的时间复杂度为O(n).
代码实现
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0, slow = 0;
while(true)
{
fast = nums[nums[fast]];
slow = nums[slow];
if(fast == slow)
break;
}
int finder = 0;
while(true)
{
finder = nums[finder];
slow = nums[slow];
if(slow == finder)
break;
}
return slow;
}
};