多数元素

一、题目描述

给定一个数组，要求求出数组中出现多数元素。多数元素是指该元素再出现次数大于数组长度的一般，。

二、解题思路

将数组中的元素统计，并比较其出现的频率。还又一种思路是投票。

三，解题方法

方法1
使用一个map集合，去统计每一个元素出现的次数，最够在比较次数，找出最多的那个输出。
代码实现：

class Solution {
    public int majorityElement(int[] nums) {

        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int num: nums){
            if(!map.containsKey(num)){
                map.put(num,1);
                
            }else{
                map.put(num,map.get(num)+1);
            }
        }

        Map.Entry<Integer,Integer> MaxEntry = null;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(MaxEntry == null || entry.getValue() > MaxEntry.getValue() ){
                MaxEntry = entry;
            }
        }

        return MaxEntry.getKey();

    }
}

方法二：投票
采用的逻辑就是使用一个标记值，标记出现最多的数。在用一个计数器。循环遍历整个数组，初始化标记值为0；当标记值为0时，赋值给一个元素。在遍历剩下的元素，当和标记值相等时，令计数器加一，不相等时减一，计数器等于0时，重新赋值。最后遍历完，标记值就是所求值，
代码实现：

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}