数组中出现次数最多的元素

leetcode 169题
Majority Element

方法一： 数组存次数，空间换时间

    public static void functionOne(int[] array){
        //局限只能100以内的数
        int[] temp = new int[100];
        for (int i=0;i< array.length ; i++){
            temp[array[i]]++;
        }

        int maxNum = 0;
        int maxElement = 0;
        for (int i:temp){
            if(temp[i] > maxNum){
                maxNum = temp[i];
                maxElement = i;
            }
        }
        System.out.println(maxElement + ":" + maxNum);
    }

HashMap的遍历
不要在for-each里add或remove元素for-each使用误区

方法二： HashMap，key存元素，value存次数，空间换时间

    public static void functionTwo(int[] array){
        Map<Integer,Integer> map = new HashMap();

        for (int i: array){
            if(map.containsKey(array[i])){
                int value = map.get(array[i]);
                map.put(array[i],value+1);
            }else {
                map.put(array[i],1);
            }
        }

        int maxNum = 0;
        int maxElement = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            if(key > maxNum){
                maxNum = key;
                maxElement = value;
            }
        }
        System.out.println(maxElement + ":" + maxNum);
    }

方法三： 当知道出现次数最多的元素过半时，可用快排的一次排序函数

    public static void functionThree(int[] array){
        int maxElement = array[0];
        int count = 1;
        for (int i= 1; i< array.length; i++){
            if(count==0){
                count++;
                maxElement = array[i];
            }else if(maxElement == array[i]){
                count++;
            }else {
                count--;
            }
        }
        System.out.println(maxElement + ":" + (count+1));
    }

方法四：当知道出现次数最多的元素过半时
蒙特卡罗算法