求一个查找数组重复元素的算法

Question

查找算法二分查找

Answer 1

不懂算法，不过你这长度java不允许

Answer 2

java的 int数组最大长度有这么大吗？

Answer 3

说的就是个意思，就是数很多，不一定就两百亿。这题的重点的算法，不是讨论int最大值或者数组最大长度

Answer 4

我觉得这个题如果改成无序数组，只有一个元素重复，用最快的算法查找到这个元素，比上述那个题难吧？  编程之美，剑指offer上有类似的题。

Answer 5

hashSet  可以排除重复的存进去 但是至于找出那一条 还要再看看

Answer 6

比如这个元素值为N，因为这个数组是已排序的1）二分查找到一个值为N的元素，记录这个位置为a
2）初始一个适宜的偏移量offset，在(a-offset, a-1) 和 (a, a+offset) 两个区间继续二分查N，找到位置a1，a2
3）递归2），offset可以适当调整，最后会得到元素值为N的 [am, an] 区间

Answer 7

有一个数字存在重复   这个条件很重要，而且数组是已经排序了的，所以你只需要比较当前这个数跟下一个输是否相等就可以了，最简单的方式就是循环
for(int i = 0; i < array.length - 1; i++){
   if(array[i] == array[i+1]){
       // 重复
      break;
   }else{
      // 不重复
   }
}

Answer 8

我记着我以前面试的时候也是有种这种类似的问题，你把数组里面的数据转换成集合有一个数字存在重复   这个条件很重要，而且数组是已经排序了的，所以你只需要比较当前这个数跟下一个输是否相等就可以了，最简单的方式就是循环
for(int i = 0; i < array.length - 1; i++){
   if(array[i] == array[i+1]){
       // 重复
      break;
   }else{
      // 不重复
   }
}本来我想转换成集合呢，但是一看这个貌似这个可以，不过这样效率是否有问题？？？？？

Answer 9

 //要查的大数组
    int[] a={1,3,5,6,6,8,11};
    //以数组的最大数为b数组的大小
    int[] b=new int[a[a.length-1]];
    
   for(int i:a)
   {
       //数组默认值为0,如果赋过值就不为0了
       if(b[i]!=0)
       {
           System.out.println("找到重复的数:"+i);
           break;
       }else
       {
           b[i]=1;
       }
   }

Answer 10

二分也是可以的，只要找到序号和数值不一致的分割点就好例如 条件，这个数后面的数 序号比数值小，前面的数字，数值跟序号相同
找到这个分割点，就是要找的数字。
不过，如果，32Bits最大可以表示40亿多一点。40/32 全部4G内存，最多可以储存大约 1 亿 数字 。
如果用位表示，可以表示4亿 数字 。
如果数据从文件读取，那么 可以用全部内存储存4亿 数字，
可以用异或运算，获取这个数据。
不过还是觉得，二分更快如果要表示 200亿需要64Bits

Answer 11

public class Test {
public static void main(String[] args) {
String[] citys = {"北京市","广州市","长沙市","海口市","中山市","白云石","海口市","南京市","重庆市","琼海市","哈哈市","喝喝试试"};
Integer i = findRepeat(citys);
System.out.println(i);
} private static Integer findRepeat(String[] citys) {
int index = 0;
for(int i=1;i<citys.length;i++){
for(int j=0;j<=index;j++){
if(citys[j]==citys[i]){
return i;
}
}
index = i;
}
return null;
}
}
跟二叉树的算法差不多，每一个元素都与之前过比较的数再做比较，相等就返回这个元素的索引，不相等就记录这个元素的索引号，用于记录遍历到哪个元素。

Answer 12

分批跑吧，在内存可承受的范围之内；
第一批结束如果没找到，第二批里包括第一批最后一个；以此类推；current=-1;
for(int i=0;i<a.length;i++)
{
   if(a[i]==current)
  return current;
   else
  current=a[i]
}
二分查找是已知数字求其位置吧还有一种节省空间的办法：bitmap
关于这个参考《编程珠玑》，翻开就看见了

Answer 13

public class Testprocess {
public static void main(String[] args) {
       Random random=new Random();
       int ss=random.nextInt(99999999);
int []a=prodcuearray(ss);
long start=System.currentTimeMillis();
for(int i=0;i<100000000;i++){
if((a[i]==a[i+1])){
System.out.println(a[i+1]);//若a[i]=1,
break;
}
}
      long end=System.currentTimeMillis();
      System.out.println("用时："+(end-start)+"毫秒");
}
public static int[] prodcuearray(int ss){
  int[]b=new int[100000000];
       int i;
       for(i=0;i<100000000;i++){
        b[i]=i;
       }        b[ss]=(ss+1);
       return b;

}}15684840
用时：26毫秒51759140
用时：72毫秒68808126
用时：111毫秒3977460
用时：12毫秒

Answer 14

public class Testprocess {
public static void main(String[] args) {
       Random random=new Random();
       int ss=random.nextInt(99999999);
int []a=prodcuearray(ss);
long start=System.currentTimeMillis();
       for(int i=0;i<4;i++){
int s=random.nextInt(4);
        for( int j=s*(a.length/4);j<(s+1)*(a.length/4)-1;j++){
         if(a[j]==a[j+1]){
         System.out.println(a[j]);
         break;
         }
        }}
      long end=System.currentTimeMillis();
      System.out.println("用时："+(end-start)+"毫秒");
}
public static int[] prodcuearray(int ss){
  int[]b=new int[100000000];
       int i;
       for(i=0;i<100000000;i++){
        b[i]=i;
       }        b[ss]=(ss+1);
       return b;

}}65050620
用时：136毫秒1469827
用时：126毫秒53486837
53486837
用时：97毫秒64116720
用时：133毫秒
 同时查找一亿个数中随机出现的相同的数。 两种方法对比发现，采用二分法  当相同的数在最后面的时候，可能一次就找出相同的数， 但是当数在前面的时候，也可能一次找不出来，用循环反而好找一些，二者各有优缺点 望楼主采纳。

Answer 15

有一个数字存在重复   这个条件很重要，而且数组是已经排序了的，所以你只需要比较当前这个数跟下一个输是否相等就可以了，最简单的方式就是循环
for(int i = 0; i < array.length - 1; i++){
   if(array[i] == array[i+1]){
       // 重复
      break;
   }else{
      // 不重复
   }
}
二分法应该是很好用的

Answer 16

是不是有那么多数先不考虑：package test;public class Test {
   public static void main(String[] args) {
      int[] data = {1,2,5,7,8,9,14,14,18,19};//数组元素是有序的（有一个数字存在重复）
      int temp;
      for (int i = 0; i < data.length; i++) {
         temp = data[i];
         if(i < data.length -1 && data[i] == data[i+1]){
            System.out.println("重复的数是："+data[i]);
         }
      }
      //重复的数是：14
   }
}

Answer 17

200亿个
什么树啊、二分啊都不行吧!量太大了。只能是分成系统可以接受的（Java支持且硬件满足条件）的数据块，一块一块查找，如果你嫌一台电脑慢，貌似现在有个词叫“分布”