服务器之家

服务器之家 > 正文

java实现二分法查找出数组重复数字

时间:2021-06-15 09:54     来源/作者:longdragen

本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部