287. 寻找重复数

题目描述

给定一个包含 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;
    }
};

287. 寻找重复数

上一篇:loj121.「离线可过」动态图连通性 题解


下一篇:P3573 [POI2014]RAJ-Rally