技巧

使用字典，边记录边比较，有直接输出。

def findDuplicate(nums):seen = {}for num in nums:if num in seen:return numseen[num] = Truereturn None

 可惜不是O(1)

二分查找

class Solution {public int findDuplicate(int[] nums) {int left=0;int right=nums.length-1;while(left<right){int mid=(left+right)/2;int count=0;for (int num:nums){if(num<=mid){count++;}}if(count<=mid){left=mid+1;}else{right=mid;}}return left;}
}