Java算法――O(n)查询数列中出现超过半数的元素 - JAVA

主要思想：

相邻元素两两比较，如果相同存入新数组，不同二者都删除。如果某数出现次数超高n/2，则最后剩下的1元素为所求。

public static int findMostElem(final ArrayList arr){  
        int size = arr.size();  
        ArrayList tmplist = (ArrayList) arr.clone();//复制数组  
        while(tmplist.size() > 1){  
            ArrayList tmp = new ArrayList




();  
            for(int i=0; i < tmplist.size()-1; i += 2){  
                if(arr.get(i)==arr.get(i+1)){  
                    tmp.add(arr.get(i));  
                }  
            }  
            tmplist = (ArrayList) tmp.clone();  
        }  
        System.out.println(tmplist.size());  
        return tmplist.get(0);  
    }