java实现二分法查找出数组重复数字
本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码，供大家参考，具体内容如下
packageoffer;
/**
*二分查找的思想来找到数组中重复的数字，时间复杂度在o(nlogn)-o(n^2)
*/
publicclassFindDuplicate3{
publicstaticvoidmain(String[]args){
intnumbers[]={0,1,2,3,4,4,6,7};//数组中的数大小从0到numbers.length-1
findDuplicate(numbers,0,numbers.length-1);
}
staticvoidfindDuplicate(intnumbers[],intleft,intright){
if(numbers==null||numbers.length==0)
return;
intmid;
while(left<=right)
{
System.out.println("Findduplicatefrom"+left+"to"+right);
mid=(left+right)/2;
if(left==right)//当两个下标值相等结束循环
{
if(countNumberInRange(numbers,left,right)>1)
{
System.out.println(left);
break;
}
elsebreak;
}
//以下通过计算在指定区间数组中数字的个数与区间的长度对比来确定数组中是否有重复数字
if(countNumberInRange(numbers,left,mid)>(mid-left+1))//如果数字区间从left到mid的数字个数大于mid-left+1则本区间肯定与重复数字
{
right=mid;
}
elseif(countNumberInRange(numbers,mid+1,right)>(right-mid))//如果数字区间从mid+1到right的数字个数大于right-mid则本区间肯定有重复数字
{
left=mid+1;
}
elseif(countNumberInRange(numbers,left,mid)==(mid-left+1)&&countNumberInRange(numbers,mid+1,right)==(right-mid))
{//因为上两个判断不能确定区间内是每个数字各出现了一次还是某个数字出现了两次，所以当左右区间长度与数字个数相等时不能排除仍然有重复数字
if(countNumberInRange(numbers,right,right)>1)//判断最后一个数字出现次数是否是多次
{
System.out.println(right);
break;
}
else//缩减区间
right=right-1;
}
}
}
//计算数组中在from到to区间数字的个数
staticintcountNumberInRange(intnumbers[],intfrom,intto)
{
intcount=0;
if(numbers==null||numbers.length==0)
return0;
for(inti=0;i=from&&numbers[i]<=to)
count++;
}
returncount;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。