leetcode 287. Find the Duplicate Number 数组重复元素查询 + 环的存在判定 + 快慢指针 + 很妙的想法

￡神魔★判官ぃ 2022-06-08 14:21 87阅读 0赞

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.

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

因为数组的内容和下标范围是一致的，所以可以考虑作为一个链表来做，我在网上看到了一个使用类似快慢指针的做法去做，想法很棒。

不过最最直接的方法还是使用HashMap来完成计数。

代码如下：

/*
     * https://discuss.leetcode.com/topic/25685/java-o-n-time-and-o-1-space-solution-similar-to-find-loop-in-linkedlist
     * 
     * 这个题很巧，可以利用寻找链表是否存在环的方法判断
     * 技巧性很强，需要好好想一下
     * */
    class Solution 
    {
        public int findDuplicate(int[] nums) 
        {
            if(nums==null || nums.length<=1)
                return 0;
            int slow=nums[0];
            int fast=nums[nums[0]];
            while(fast!=slow)
            {
                slow=nums[slow];
                fast=nums[nums[fast]];
            }
            slow=0;
            while(fast!=slow)
            {
                slow=nums[slow];
                fast=nums[fast];
            }
            return slow;
        }
    }

下面是C++的做法，就是使用双指针做一个遍历，注意这个题很巧妙，可以使用双指针来做。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findDuplicate(vector<int>& a) 
        {
            int slow = a[0];
            int fast = a[slow];
            while (fast != slow)
            {
                slow = a[slow];
                fast = a[a[fast]];
            }
            slow = 0;
            while (fast != slow)
            {
                slow = a[slow];
                fast = a[fast];
            }
            return fast;
        }
    };