287. Find the Duplicate Number

蠻有意思的一個題目,

首先, 假如數字1- 6中, 像下面這樣

[1,2,3,3,4,5,6]

有七個數字, 問你誰多出來了

以排序的情況下我們肉眼馬上就看出來了, 但題目是給你一個亂數且告知你不准改變array的排序

但根據上面的題目, 正常來說6個數字中, 最大值是6, 最小值是1,

中間值是3.5, 因為這邊都是整數, 所以我們可以檢查小於等於三的

理論上, 應該只有三個數字, 但這時我們全部算算

[1,2,3,3], 共四個

代表一定一個人多出來了, 所以我們馬最大值更新到3,

下一輪的中間值是 2, 所以我們看小於等於2的是不是只有兩個

發現, 對誒只有兩個, 所以範圍馬上就在縮到[3, 3]

等等, 就剩你們兩個了, 那就抓到你了

這個方法相當於做了O(logn * n)的時間複雜度

class Solution {
  public:
    int findDuplicate(vector<int> &nums) {
int max_number = nums.size() - 1;
        int min_number = 1;
        while (min_number < max_number) {
            int mid_num = (min_number + max_number) / 2;
            int count = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] <= mid_num) {
                    count++;
                }
            }
            if (count <= mid_num) {
                min_number = mid_num + 1;
            } else {
                max_number = mid_num;
            }
        }
        return max_number;
    }
};

但這題有一個更厲害的方法

Find the Duplicate Number

可以參考他寫的, 一定比我隨便筆記還詳細

時間複雜度為O(n)

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