1.題目描述

2.思路

3.代碼實現

public class H287 {public int findDuplicate(int[] nums) {// 重復數字可能的最小值int min=1;// 重復數字可能的最大值，數組長度為 n，數字范圍是 [1, n-1]int max=nums.length-1;while(min<max) {// 防止溢出，取中點int mid = min + (max - min) / 2;int cnt = 0;for (int i = 0; i < nums.length; i++) {// 統計數組中落在 [min, mid] 區間的數字個數if (min <= nums[i] && nums[i] <= mid) {cnt++;}}if(cnt>mid-min+1) {// 如果統計數大于區間長度，說明重復數字在左區間max=mid;}else {// 否則重復數字在右區間min=mid+1;}}// 循環結束時，min 就是重復數字,當max=min說明找到這個數了return min;}public static void main(String[] args){H287 test=new H287();int[] nums = {1,3,4,2,2};int res=test.findDuplicate(nums);System.out.println(res);}
}