[LeetCode]287. Find the Duplicate Number

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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. 

1
2
3
4
5
6
7
8
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(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution

Analysis

题目给定一个长度为n+1的数组, 数组中每个数字在[1,n]之间, 证明至少存在一个重复数字. 假设只有一个重复数字,找到这个数字.

如果只有这些背景的话,不可能被标为medium. 用hash表就可以解决. 但是题目还有额外要求:

  1. 数组只读,不能修改—-不能用数组中的数字做下标,移动数组: 这样移动后nums[i] = i+1, 当nums[i] == nums[j]说明重复, 返回这个数; 同时不能使用排序
  2. 常量空间—-不能使用hash表: O(n); 也不能创建新数组再排序
  3. 时间复杂度小于O(N*N)—不能用循环,暴力破解
  4. 只有一个数字重复,但可能重复多次(不仅一次).

在限制条件下, 我没有思路Sad…

看大佬的答案.使用二分查找. 二分查找要求数组是有序的, 而这里数组并不有序. 所以需要对二分查找做一个小变化, 我们对[1,n]这个有序区间进行二分, 对其中每个数num,计算小于等于num的数字的个数, 如果小于等于num,说明[1,num]不存在重复数字[1-num有这么多坑,现在正好填满, 而数组还有重复元素,说明在另外一个区间里],只可能在(num, n]之间, 反之.

还有另一种解法. 将这个数组看做链表. 用数组模拟链表, 如下图所示.

1.png

索引表示链表节点的值,元素值表示next指针. 由于这里存在重复元素, 也就是说这个链表存在环. 所以我们的问题就变成查找链表环的入口节点[这个入口节点就是重复节点].

比如例一: 

1
2
3
[1,3,4,2,2]. 

对应的链表为: 1->3->2->4->2. 重复节点是2.

类似查找链表的环入口节点, 可以参考剑指offer中链表中环的入口结点的解法.链表环的入口节点,我通常先使用一个快慢指针判断是否有环, 然后返回相遇节点, 然后再判断环的长度; 之后再用快慢指针,慢指针从头开始,快指针先走环的长度,然后当两个指针相遇时,就是环的入口节点.

还有另一种方法: 先用快慢指针,慢指针一次走一步,快指针走两步,判断是否有环; 然后慢指针重置为链表头,两个指针同时走,直到相遇,相遇节点就是重复节点,或者说入口节点[我是死记硬背的,原理不太清楚].

Code

Solution One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // 统计个数: 统计小于等于mid的个数
        int left = 1, right = nums.size()-1;
        
        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;
    }
};

Solution Two 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;// 找到环, slow是环内节点
        }
        while (true) {
            slow = nums[slow];// 同时走
            t = nums[t];// t初始为头结点
            if (slow == t) break;// 相遇,found
        }
        return slow;
    }
};

References

https://www.cnblogs.com/grandyang/p/4843654.html

http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/

Conclusion

Binary Search: 要求一个区间有序. 一般情况下是数组区间有序, 这道题给我一个提示, 也可以是查找区间有序(要找的数的区间有序), 但数组并不有序,而是数组数的范围有序, 比如这里有序区间是[1,n]. 而且,刚开始我看到标签有binary search二分查找, 也想到了对[1,n]区间划分, 但之后我想的是对每个数组查找有多少个等于这个数字的个数, 并不是小于等于, 所以之后的区间再细分,无从下手了. 重点是: 有序区间, 区间细分, 根据mid的情况, 是左区间,还是右区间. 判断条件是什么? 想清楚这两个问题就可以使用二分查找, 要学会算法贯通, 找到算法的本质特性, 方便其通用性.

您的支持就是我更新的最大动力!谢谢!