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

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • java实现数组中的逆序对

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对,例如在数组{7,5,6,4}中,一共存在5对逆序对,分别是{7,6},{7,5},{7,4},{6,4},{5,4}.输入一个数组,求出这个数组中的逆序对的总数P.并将P对1000000007取模的结果输出.,即输出P%1000000007. 代码 解法一 暴力简单低效,不会改变原数组 public static int inversePairs(int[] array) { if (array == null ||

  • 浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    一直到大四才开始写自己的第一篇博客,说来实在有点羞愧.今天写了关于排序的算法题,有插入排序,冒泡排序,选择排序,以下贴上用JAVA实现的代码: public class test5 { public static void print(int []array) //输出数组方法 { for(int i=0;i<array.length;i++) System.out.print(" "+array[i]); } public static void selectsort(int

  • Java算法实现调整数组顺序使奇数位于偶数之前的讲解

    调整数组顺序使奇数位于偶数之前 1. 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 2. 题目分析 该题目类似于一个选择排序,将奇数选择出来,放置于数据前面的位置,保持其他未被选择的元素的相对位置不变: 1. 遍历数组,当数组元素为奇数是进行处理,判断条件为 n % 2 != 0 2. 设置一个变量标注当前已遍历的元素中奇数的个数oddNum,也是将该奇数元素

  • Java中数组在内存中存放原理的讲解

    Java中数组在内存中存放原理的讲解

    Java中数组被实现为对象,它们一般都会因为记录长度而需要额外的内存.对于一个原始数据类型的数组,一般需要24字节的头信息再加上保存值所需的内存,其中24字节的头信息分别包含以下几个部分. 下面分别分析一维.二维.三维的数组存储情况. 下面首先对一维数组进行分析,以int[]型数组为例,假设数组长度为N,那么需要的内存占用(24+4N)个字节,原因分析比较简单,图解示例如下:即占用内存总量=头信息内存+数组N个int值占用内存. 对于二维数组进行分析,首先对于多维数组的概念,大家可以参考这篇文章

  • Java如何找出数组中重复的数字

    题目描述:找出数组中重复的数字,具体内容如下 在一个长度为n的数组里的所有数字都在 0~n-1的范围内.数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如:如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出的是重复的数字2或者3 这个面试题是剑指offer中的面试题3,,下面我用java代码实现. 算法步骤: 从头到尾依次扫描数组中的每个数字. 1. 当扫描到下表为i的数字时,首先比较这个数字(用m表示)是不是等

  • Java实现删除排序数组中重复元素的方法小结【三种方法比较】

    本文实例讲述了Java实现删除排序数组中重复元素的方法.分享给大家供大家参考,具体如下: 题目描述: 给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度. 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成. 一:通过ArrayList解决 时间复杂度和空间复杂度都为O(n) ArrayList<Integer> list = new ArrayList<Integer>(); // 去掉数组中重复的元素 public int r

  • Java数组高级算法与Arrays类常见操作小结【排序、查找】

    Java数组高级算法与Arrays类常见操作小结【排序、查找】

    本文实例讲述了Java数组高级算法与Arrays类常见操作.分享给大家供大家参考,具体如下: 冒泡排序 冒泡排序原理 冒泡排序代码: package cn.itcast_01; /* * 数组排序之冒泡排序: * 相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处 */ public class ArrayDemo { public static void main(String[] args) { // 定义一个数组 int[] arr = { 24, 69, 80, 57,

  • java集合与数组的相同点和不同点

    数组: 数组可以用来保存多个基本数据类型的数据,也可以用来保存多个对象. 数组的长度是不可改变的,一旦初始化数组时就指定了数组的长度(无论是静态初始化还是动态初始化). 数组无法保存具有映射关系的数据. 集合: 集合是只用于存储数量不等的对象. 集合的长度是可变的. 集合可以保存具有映射关系的数据. 相同点: 数组和集合类同是容器. 不同点: 数组的长度是固定的,集合的长度是可变的. 数组只能存储同类型的对象,集合可以存储不同类型的对象. 集合只能存储对象不能存储基本类型 总结 以上就是这篇文章

  • Java Scanner输入两个数组的方法

    题目 从命令行读入两个数组的长度和数组的值,其中第一行两个数na和nb代表aa和bb数组的长度 代码 import java.util.Scanner; public class Z { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int na = scanner.nextInt(); int nb = scanner.nextInt(); int[] aa = new in

  • Java中字符数组和字符串与StringBuilder和字符串转换的讲解

    1.字符串->字符数组: String str = "abc": char[] a = str.toCharArray(); 记忆:字符串是个类,所以用内建函数 延伸: char b = str.charAt(1); str.length(); a.length; 2.字符数组->字符串: String str = String.valueOf(a): 记忆:类似强制类型转换格式,String(a) 延伸:字符转字符类 Character c = Character.val

随机推荐