Question

面试题：有一个100万的数组，里边有两个是重复的，如何设计算法找到。

请给出科学的解决办法？ 我想100万的数组肯定不能再用循环找出吧！

Answer 1

//100万不是很大
import java.util.*;
public class Test{

public static void main(String[] args){

int[] a = new int[1000000];

for(int i = 0; i<1000000;i++){
a[i] = i+1; //从1--1000000没有重复的
}

a[355] = 100;//将第356个数改成100，这样就只有两个重复的数100

List<Integer> list = new ArrayList<Integer>();

for(int i = 0 ; i < 1000000;i++){
Integer temp = new Integer(a[i]);
if(!list.contains(temp)){
list.add(temp);
}else{
int j = list.indexOf(temp) ;//第一次出现
System.out.println("第"+(j+1)+"个数和第"+(i+1)+"个数重复为："+temp);
break; //找到即退出
}
}

}
}

Answer 2

肯定得循环找
但是先排序没有必要 运算量太大
我错了 写的算法复杂度太高 运算量太大 等等 正在优化

Answer 3

先排序,再找,也许排序的时候就找到了.

Answer 4

hash table