leetcode 169. Majority Element

Seawolf

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

class Solution {
    public int majorityElement(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) {
            
            map.put(i, map.getOrDefault(i,0)+1);
            if(map.get(i) > (nums.length/2)){
                return i;
            }

        }
        
        return -1;
        
    }
}

bucket sort!!

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) map.put(i, map.getOrDefault(i,0)+1);
        
        List<Integer>[] bucket = new List[nums.length+1];
        
        for(Integer i : map.keySet()){
            
            int fre = map.get(i);
            if(bucket[fre] == null) bucket[fre] = new ArrayList<>();
            
            bucket[fre].add(i);
        }
        List<Integer> list =new ArrayList<>();
        for(int i = bucket.length -1 ; i >= 0 && list.size()<=1; i--)
            if(bucket[i] != null)
                list.addAll(bucket[i]);
        
        return list.get(0);
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        
        int res = nums[0];
        int fre = 1;
        
        for(int i = 1; i < nums.length; i++){
            
            if(nums[i] == res) fre ++;
            else fre --;
            
            if(fre == 0) {
                
                res = nums[i];
                fre = 1;
            }
        }
        return res;
        
    }
}