AC c++ code with O(n) time and O(1) space.


  • 26
    T

    Please read the link to understand it:http://keithschwarz.com/interesting/code/?dir=find-duplicate

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int l=nums.size();
            int slow =l-1;int fast = l-1;
            while(1){
                slow=nums[slow]-1;
                fast=nums[nums[fast]-1]-1;
                if(slow == fast){
                    break;
                }
            }
            fast = l-1;
            while(1){
                slow=nums[slow]-1;
                fast=nums[fast]-1;
                if(slow==fast)return slow+1;
            }
            
        }
    };

  • 0
    L

    Nice Solution!


  • 2

    Great! I am very interested in how you find that nice link :-) BTW, I rewrite your code, mainly replacing the while(1) ... if(...) break with do-while, which finds its applications in such a problem :-)

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int n = nums.size(), slow = n - 1, fast = n - 1;
            do {
                slow = nums[slow] - 1;
                fast = nums[nums[fast] - 1] - 1;
            } while (slow != fast);
            fast = n - 1; 
            do {
                slow = nums[slow] - 1;
                fast = nums[fast] - 1;
            } while (slow != fast);
            return slow + 1;
        }
    };

  • 0
    T

    I found it from the previous post:http://stackoverflow.com/questions/7117388/finding-out-the-duplicate-element-in-an-array . In the end it says python implementation.:):)


  • -5
    S

    Is there any assumption made? It cannot pass the case [3,2,1,2]


  • 0

    Well, this post has got 10 upvotes, which means many people have tested it on the OJ and got accepted. Could you double check your version before making such a judgement?


  • 0

    @jianchao.li.fighter I once came across a "solution" that had +8 votes even though it was obviously wrong :-)


  • 0
    T

    So brilliant. I think the hardest part is turning this problem into a cycle detection one by applying the function mapping. Then the cycle detection is pretty much like the LinkList Cycle Detection II.


  • 0
    Z

    Both the solution and the link are very nice. Thank you!


  • 5
    J

    Why are you guys start from the last one. It will be neat and clear if you start from the first one.

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

  • 0

    You had better replied to jianchao.li.fighter's answer, that way both of them would get notified.

    Anyway, it seems rather clear that they do it that way because of Keith's original, where the input contained numbers from 0 to n-2.


  • 0
    S

    Such a brilliant solution! Thank you!


  • 0
    S

    The code is so brilliant.Thank you!


  • 1
    O

    Has to say this is actually wrong, and it only passed OJ by luck; One key point of the algorithm is the starting point has to be guaranteed out of loop, and neither on a independent closed loop. (Think about the graph, it is not guarantee that all the nodes will together form a giant rho graph, instead, there could be several independent closed loops existing, like 1->1, or 2->3->4->2, if you happened to pick the starting point in any of these closed loops, you are doomed). Thats why the problem gave array of length n+1 (index 0 to n), and make the value range 1 to n, that makes 0 the special point, whose value must point to the real rho graph, not any closed loop. And a correct solution must select 0 as the starting point.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.