# 287 - Find the Duplicate Number

解法一 - Cyclic Sort

我們可以照之前的 pattern,先做完 cyclic sort,然後再找出跟 index 對不上的 element,那個 element 就是 duplicate 的 number。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;

            if(j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // If the number do not match the index, that's the duplicate number
        int duplicate;
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                duplicate = nums[i];
                break;
            }
        }

        return duplicate;
    }
};

解法二 - 稍微優化版的 cyclic sort

我們知道,因為有 duplicate 存在,所以只要在 cyclic sort 過程中,有看到 nums[i] == nums[j] 的話,那就表示找到 duplicate number 了。要注意 nums[i] 不能等於 i+1,因為 j 就會等於 i,那 nums[i] 當然就會等於 nums[j] 了。

這樣做的好處是不需要最後再走過一遍 array。

實作如下:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            if(nums[i] != i + 1) {
                int j = nums[i] - 1;

                if(nums[i] != nums[j]) {
                    swap(nums[i], nums[j]);
                }
                else{
                    return nums[i];
                }
            }
            else {
                ++i;
            }
        }

        return -1;
    }
};

Last updated