leetcode287

蔚落 2022-08-09 00:51 120阅读 0赞

目前最新的题目吧。

Find the Duplicate Number

官方给的难度是hard，但感觉其实通过挺简单的。

这道题目的意思是在n+1大小的数组中有范围在1~n的数

要求找出相同的一个数。

限制比较多：

1.不能修改数组

2.时间复杂度要求

3.不能有多余空间

直到写这篇博客前，才注意原来不能修改数组，不过我先排序，再在有序数组中找到重复数字的代码居然通过了。。

先给出代码，下来找到不修改数组的方法后再来更博：

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            int i;
            for(i=0;i<nums.size();i++)
            {
                if(nums[i]==nums[i+1])
                    break;
            }
            return nums[i];
        }
    };

=============================2015/09/30晚更新=================================================

发现这道题目的真实限制之后，久久不能释怀。不能移动数组这个约束，让我难受了好几天。

在论坛学习到了大神的思路（鸽巢原理）：

n个笼子（表示数字范围1~n），却有n+1只鸽子（表示数组大小，即有n+1个数，每只鸽子表示一个数），则必然有一个数字（笼子）对应两只及以上的鸽子（数）

思路，首先找到这些数字的中数，由于数字是1~n，一开始这个数字时 （n+1）/2

然后拿数组中的数与中数比较，当比中数小的数>中数 （这个道理举个例子就能看清）：则说明重复的数在中数的左边，即比中数小

这样我们将重新对中数左边的部分进行上述比较（这里实际上隐式的维护了一个1～n的数组）。

还是看代码比较清晰：

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
    		int i;
    		int vecLen = nums.size();
    		int low = 1;
    		int high = vecLen-1;
    		while(low < high)
    		{
    			int mid = (high  + low) / 2;		
    			int count = 0;
    			for(i=0;i<vecLen;i++)
    			{
    				if(nums[i]<=mid)
    					count ++;
    			}
    			if(count > mid)
    			{
    				high = mid;
    			}
    			else
    			{
    				low = mid+1;
    			}
    		}
    		return low;
        }
    };