287. Find the Duplicate Number

 

Given an array  nums  containing  n  + 1 integers where each integer is between 1 and  n  (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant,  O (1) extra space.
  3. Your runtime complexity should be less than  O ( n 2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

 

这道题给了我们 n+1 个数,所有的数都在 [1, n] 区域内,首先让证明必定会有一个重复数,这不禁让博主想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理),即如果有十个苹果放到九个抽屉里,如果苹果全在抽屉里,则至少有一个抽屉里有两个苹果,这里就不证明了,直接来做题吧。题目要求不能改变原数组,即不能给原数组排序,又不能用多余空间,那么哈希表神马的也就不用考虑了,又说时间小于 O(n2),也就不能用 brute force 的方法,那也就只能考虑用二分搜索法了,在区间 [1, n] 中搜索,首先求出中点 mid,然后遍历整个数组,统计所有小于等于 mid 的数的个数,如果个数小于等于 mid,则说明重复值在 [mid+1, n] 之间,反之,重复值应在 [1, mid-1] 之间,然后依次类推,直到搜索完成,此时的 low 就是我们要求的重复值,参见代码如下:

 

解法一:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1, right = nums.size();
        while (left < right){
            int mid = left + (right - left) / 2, cnt = 0;
            for (int num : nums) {
                if (num <= mid) ++cnt;
            }
            if (cnt <= mid) left = mid + 1;
            else right = mid;
        }    
        return right;
    }
};

 

经过热心网友 waruzhi 的留言提醒还有一种 O(n) 的解法,并给了参考帖子,发现真是一种不错的解法,其核心思想快慢指针在之前的题目 Linked List Cycle II 中就有应用,这里应用的更加巧妙一些,由于题目限定了区间 [1,n],所以可以巧妙的利用坐标和数值之间相互转换,而由于重复数字的存在,那么一定会形成环,用快慢指针可以找到环并确定环的起始位置,确实是太巧妙了!

 

解法二:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0, t = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        while (true) {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) break;
        }
        return slow;
    }
};

 

这道题还有一种位操作 Bit Manipulation 的解法,也十分的巧妙。思路是遍历每一位,然后对于 32 位中的每一个位 bit,都遍历一遍从0到 n-1,将0到 n-1 中的每一个数都跟 bit 相 ‘与’,若大于0,则计数器 cnt1 自增1。同时0到 n-1 也可以当作 nums 数组的下标,从而让 nums 数组中的每个数字也跟 bit 相 ‘与’,若大于0,则计数器 cnt2 自增1。最后比较若 cnt2 大于 cnt1,则将 bit 加入结果 res 中。这是为啥呢,因为对于每一位,0到 n-1 中所有数字中该位上的1的个数应该是固定的,如果 nums 数组中所有数字中该位上1的个数多了,说明重复数字在该位上一定是1,这样我们把重复数字的所有为1的位都累加起来,就可以还原出了这个重复数字,参见代码如下:

 

解法三:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int res = 0, n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int bit = (1 << i), cnt1 = 0, cnt2 = 0;
            for (int k = 0; k < n; ++k) {
                if ((k & bit) > 0) ++cnt1;
                if ((nums[k] & bit) > 0) ++cnt2;
            }
            if (cnt2 > cnt1) res += bit;
        }
        return res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/287

  

类似题目:

First Missing Positive

Missing Number

Single Number

Find All Numbers Disappeared in an Array

Set Mismatch

Array Nesting

Linked List Cycle II

 

参考资料:

https://leetcode.com/problems/find-the-duplicate-number/

https://leetcode.com/problems/find-the-duplicate-number/discuss/72872/O(32*N)-solution-using-bit-manipulation-in-10-lines

https://leetcode.com/problems/find-the-duplicate-number/discuss/73045/Simple-C%2B%2B-code-with-O(1)-space-and-O(nlogn)-time-complexity

https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation