// @Title: 库存管理 II (库存管理 II)
// @Author: qisiii
// @Date: 2022-02-21 14:28:58
// @Runtime: 1 ms
// @Memory: 44.5 MB
// @comment: 投票法
// @flag: BLUE
class Solution {
     public int majorityElement(int[] nums) {
       int max=nums[0];int maxCount=1;int count=1;
       while(count<nums.length){
           if(nums[count]==max){
               maxCount++;
           }else{
               maxCount--;
           }
           if(maxCount==0){
               max=nums[count];
               maxCount=1;
           }
           count++;
       }
       return max;
    }
}

// @Title: 库存管理 II (库存管理 II)
// @Author: qisiii
// @Date: 2022-02-21 14:16:50
// @Runtime: 2 ms
// @Memory: 44.5 MB
// @comment: 排序
// @flag: ORANGE
class Solution {
     public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

// @Title: 库存管理 II (库存管理 II)
// @Author: qisiii
// @Date: 2022-02-21 14:13:11
// @Runtime: 16 ms
// @Memory: 46.6 MB
// @comment: hash
// @flag: BLUE
class Solution {
     public int majorityElement(int[] nums) {
        int ban=(nums.length-1)/2;
        Map<Integer,Integer> map=new HashMap(ban);
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else{
                map.put(i,1);
            }
            if(map.get(i)>ban){
                return i;
            }
        }
        return -1;
    }
}