java实现二分法查找出数组重复数字
作者:longdragen 时间:2022-07-15 03:54:00
本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下
package offer;
/**
* 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2)
*/
public class FindDuplicate3 {
public static void main(String[] args) {
int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数 大小从0 到 numbers.length-1
findDuplicate(numbers,0,numbers.length-1);
}
static void findDuplicate(int numbers[],int left,int right){
if (numbers == null || numbers.length == 0)
return;
int mid;
while(left<=right)
{
System.out.println("Find duplicate from "+left+" to "+right);
mid=(left+right)/2;
if(left==right)//当两个下标值相等结束循环
{
if(countNumberInRange(numbers,left,right)>1)
{
System.out.println(left);
break;
}
else break;
}
//以下通过计算在指定区间数组中数字的个数与区间的长度对比来确定数组中是否有重复数字
if(countNumberInRange(numbers,left, mid)>(mid-left+1))//如果数字区间从left到 mid的数字个数大于mid-left+1 则本区间肯定与重复数字
{
right=mid;
}
else if(countNumberInRange(numbers,mid+1, right)>(right-mid))//如果数字区间从mid+1到right的数字个数大于right-mid则本区间肯定有重复数字
{
left=mid+1;
}
else if(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区间数字的个数
static int countNumberInRange(int numbers[],int from,int to)
{
int count=0;
if(numbers==null || numbers.length==0)
return 0;
for(int i=0;i<numbers.length;i++)
{
if(numbers[i]>=from && numbers[i]<=to)
count++;
}
return count;
}
}
来源:https://blog.csdn.net/longdragen/article/details/77373846
标签:java,二分法,数组
0
投稿
猜你喜欢
Android使用phonegap从相册里面获取照片(代码分享)
2023-07-24 18:53:03
C# ADO.NET 离线查询的实现示例
2023-06-12 00:52:03
java8 多个list对象用lambda求差集操作
2022-02-19 06:26:52
C#中英文混合字符串截取函数
2023-01-19 06:02:55
c# 判断指定文件是否存在的简单实现
2023-10-16 01:39:54
解决BigDecimal转long丢失精度的问题
2022-07-16 13:44:22
浅析Java中接口和抽象类的七大区别
2022-01-16 21:09:36
C#生成EMF矢量图形文件示例详解
2022-10-30 02:12:56
Spring Cloud 动态刷新配置信息教程详解
2023-12-02 04:48:16
Spring Security实现自动登陆功能示例
2023-01-29 15:31:55
CentOS安装jdk的三种方法
2022-01-13 06:24:41
springcloud注册hostname或者ip的那些事
2022-05-06 00:57:37
java获取ip地址示例
2021-12-25 07:04:22
C#之set与get方法的用法案例
2021-08-09 01:17:18
Android调用手机摄像头拍照和录音功能
2022-10-22 15:37:16
SpringBoot启动yaml报错的解决
2021-09-09 22:58:14
Unity中的PostProcessScene实用案例深入解析
2021-06-09 04:57:28
在IDEA中 实现给main方法附带参数的操作
2022-10-23 14:42:03
c语言switch反汇编的实现
2023-06-29 03:38:17
Java女装商城系统的实现流程
2023-09-23 11:53:51