Easily understand-able analysis and my cpp code with O(N) time constant space


  • 1
    Y

    The numbers in question are within range [1, n], which is very important. It implies that each element corresponds to an index of nums, which gives us a linked list with a circle.
    So, this problem can be transformed into finding the entry point of the circle in a linked list.

    class Solution {
    public:
        
        int findDuplicate(vector<int>& nums) {
            int slow = 0, fast = 0;
            auto move = [&nums] (int index) {
                return nums[index];
            };
            slow = move(slow);
            fast = move(move(fast));
            while (slow != fast) {
                slow = move(slow);
                fast = move(move(fast));
            }
            fast = 0;
            while (slow != fast) {
                slow = move(slow);
                fast = move(fast);
            }
            return slow;
        }
    };
    

Log in to reply
 

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