package com.breakpoint.code;
/**
* 287. 寻找重复数
*
* @author breakpoint
*
*/
public class Main287 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = { 1, 3, 4, 2, 1 };
int target = new Main287().findDuplicate(nums);
System.out.println(target);
}
public int findDuplicate(int[] nums) {
int l = 1, r = nums.length - 1, count = 0, targetCount = 0;
int target = (l + r) / 2;
while (l <= r) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] < target) {
count++;
}
if (nums[i] == target) {
count++;
targetCount++;
}
}
if (count > target) {
if (targetCount > 1) {
return target;
}
r = target - 1;
target = (l + r) / 2;
} else {
l = target + 1;
target = (l + r) / 2;
}
count = 0;
targetCount = 0;
}
return -1;
}
}