287. Find the Duplicate Number - cocoder39/coco39_LC GitHub Wiki

287. Find the Duplicate Number

2020 Notes:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for num in nums:
            if nums[abs(num)-1] < 0:
                return abs(num)
            else:
                nums[abs(num)-1] *= -1

This solution modifies original input. The 2 solutions listed below are also interesting

============================================================

fast and slow pointers : O(n)

take advantage of 142. Linked List Cycle II

index of number 1 ... n is from 0 to n, thus nums[0] != 0. suppose nums[0] = a, then nums[a] != a if there is no duplication and so on. Hence, if it would generate a singly linked list starting from 0 if there is no duplication. In other words, no two index for same number.

0  a  b  c
a  b  c

num[c] = newly_appeared_number, then go on; = a or b or c, then a cycle two index points to the same number, thus the number's in degree is 2, it is the entry of the cycle

int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

binary search: O(n * log n)

if memory is not an issue, we can use hash or bucket sort, which take O(n) time and O(n) memory. Since we only have O(1) memory, and the desired time is less than O(n ^ 2). what we can achieve is O(n log n) time under O(1) memory. Try binary search.

given n + 1 numbers, all of them are within [1, n]. binary search takes O(log n), a traversal takes O(n). Consider traversal inside binary search.

main idea: each time we guess the duplication is mid. First consider if there is no duplication. then the number of elements that <= mid should be equal to mid, regardless that n is even or odd.

int findDuplicate(vector<int>& nums) {
        int start = 1, end = nums.size() - 1; //end = n
        while (start + 1 < end) {
            int mid = start + (end - start) / 2; //guessed duplication
            int cnt = 0;
            for (auto num : nums) {
                //cnt == mid if no duplication
                cnt += (num <= mid);
            }
            
            if (cnt > mid) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        
        int cnt = 0;
        for (auto num : nums) {
            cnt += (start == num);
        }
        if (cnt > 1) {
            return start;
        }
        return end;
    }
⚠️ **GitHub.com Fallback** ⚠️