LeetCode 287. Find the Duplicate Number【Java】

題目描述

Find the Duplicate Number

AC代碼

/*
解題根據：抽屜原理
時間複雜度：O(nlogn),二分->logn 周遊->n n*logn=nlogn
*/

class Solution {
    public int findDuplicate(int[] nums) {
        int l=1,r=nums.length-1;
        while(l<r){
            int mid=l+r>>1;
            //蘋果的個數
            int cnt=0;
            for(int x:nums)
                if(x>=l&&x<=mid)
                    cnt++;
            //mid-l+1可以看作是抽屜的個數
            if(cnt>(mid-l+1))
                //滿足則說明l~mid區間中有重複的數字
                r=mid;
            else
                //不滿足則說明l~mid區間沒有重複的，需要到mid+1~r區間檢視是否有重複的數字
                l=mid+1;
        }
        return r;
    }
}