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);}
}