剑指 Offer 39. 数组中出现次数超过一半的数字

解题思路

HashMap比较好理解，遍历一遍数组，取得众数

关键是投票法

思想就是一票抵一票，即使是最差的情况，每一个非众数的数都和众数去抵消，众数仍然有余

首先判断cnt是否为0

如果 cnt==0，那么就将新的数假设为众数 ans，并进行 cnt++ 如果 cnt!=0，那么就需要判断当前的数，是否和已经存在的ans相同，如果相同，那么cnt+1，如果不相同，那么 cnt-1

代码

class Solution {
          
   
    public int majorityElementA(int[] nums) {
          
   
        // HashMapm，时间复杂度为O(n)，空间复杂度为O(n)
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i: nums){
          
   
            int cnt = map.getOrDefault(i,0)+1;
            map.put(i,cnt);
            if(cnt > nums.length/2) return i;
        }
        return nums.length==0 ? 0 : nums[0];
    }
    public int majorityElement(int[] nums) {
          
   
        // 使用投票法，一票抵一票，两个不相同的数相互抵消，最差的情况，每一个非众数都和众数抵消，但是此时众数仍然有余
        int cnt=0, ans=0;
        for(int num:nums){
          
   
            if(cnt==0){
          
   
                cnt++;
                ans = num;
            }else{
          
   
                cnt += num==ans ? 1 : -1;
            }
        }
        return nums.length==0 ? 0 : ans;
    }
}