gpt4 book ai didi

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

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java实现二分法查找出数组重复数字由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

本文实例为大家分享了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 。

最后此篇关于java实现二分法查找出数组重复数字的文章就讲到这里了,如果你想了解更多关于java实现二分法查找出数组重复数字的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com