有一个100万的数组，里边有两个市重复的，如何设计算法找到

 

package com.xiva.demo;

import java.util.*;
public class ArrayDemo{


    @SuppressWarnings("rawtypes")
	public static void main(String[] args){
    	
    	Date starTime = new Date();
    	System.out.println(starTime);
        int[] a = new int[1000000];

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

        a[377455] = 	100;
//        Date endTime = new Date();
//    	System.out.println(endTime);
    	
    	
//        List<Integer> list = new ArrayList<Integer>();
        Set set=new HashSet();
//        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;  //找到即退出
//            }
//        }
        int i = 0;
        for( i=0;i<a.length;i++)
        {
         if(!set.add(a[i]))
        	 break;
        }
        Iterator itreator = set.iterator();
        int j = 1;
        while(itreator.hasNext()){
        	int temp = Integer.parseInt(itreator.next().toString());
        	if(temp == a[i])
        		break;
        	j++;
        }
        System.out.println(i);
        System.out.println(j);
        System.out.println("the same number is "+a[i]);
        
        Date endTime = new Date();
    	System.out.println(endTime);

    }
}

 HashSet的效率要高多了啊；还有其转换的Iterator遍历效率也不错~

 

 

 

package com.xiva.demo;

import java.util.*;
public class ArrayDemo{

    @SuppressWarnings({ "rawtypes", "unchecked" })
	public static void main(String[] args){
    	
    	Date starTime = new Date();
    	System.out.println(starTime);
        int[] a = new int[1000000];

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

        Set set=new LinkedHashSet();//为有序hashSet
//        Set set=new HashSet();
        int index = 0;
        for( index=0;index<a.length;index++)
        {
         if(set.contains(a[index]))
        	 break;
         else{
        	 synchronized (set) {
        		 set.add(a[index]);
			}
        	
         }
        }
        Iterator itreator = set.iterator();
        int j = 1;
        while(itreator.hasNext()){        	
        	Object obj = itreator.next();
        	int temp = Integer.parseInt(obj.toString());
        	if(temp == a[index])
        		break;
        	j+=1;      	
        }
        System.out.println(index);
        System.out.println(j);
        System.out.println("the same number is "+a[index]);
        
        Date endTime = new Date();
    	System.out.println(endTime);

    }
}

 

LinkedHashSet为有序类