leetcode 169. Majority Element

Seawolf

1. Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
   
2. 
   
3. You may assume that the array is non-empty and the majority element always exist in the array.
   
4. 
   
5. Example 1:
   
6. 
   
7. Input: [3,2,3]
   
8. Output: 3
   
9. Example 2:
   
10. 
    
11. Input: [2,2,1,1,1,2,2]
    
12. Output: 2

复制代码

1. class Solution {
   
2.     public int majorityElement(int[] nums) {
   
3.         if (nums.length == 0) return 0;
   
4.         if (nums.length == 1) return nums[0];
   
5.         Map<Integer, Integer> map = new HashMap<>();
   
6.         for(int i : nums) {
   
7.             
   
8.             map.put(i, map.getOrDefault(i,0)+1);
   
9.             if(map.get(i) > (nums.length/2)){
   
10.                 return i;
    
11.             }
    
12. 
    
13.         }
    
14.         
    
15.         return -1;
    
16.         
    
17.     }
    
18. }

复制代码

bucket sort!!

1. class Solution {
   
2.     public int majorityElement(int[] nums) {
   
3.         Map<Integer, Integer> map = new HashMap<>();
   
4.         for(int i : nums) map.put(i, map.getOrDefault(i,0)+1);
   
5.         
   
6.         List<Integer>[] bucket = new List[nums.length+1];
   
7.         
   
8.         for(Integer i : map.keySet()){
   
9.             
   
10.             int fre = map.get(i);
    
11.             if(bucket[fre] == null) bucket[fre] = new ArrayList<>();
    
12.             
    
13.             bucket[fre].add(i);
    
14.         }
    
15.         List<Integer> list =new ArrayList<>();
    
16.         for(int i = bucket.length -1 ; i >= 0 && list.size()<=1; i--)
    
17.             if(bucket[i] != null)
    
18.                 list.addAll(bucket[i]);
    
19.         
    
20.         return list.get(0);
    
21.     }
    
22. }

复制代码

1. class Solution {
   
2.     public int majorityElement(int[] nums) {
   
3.         
   
4.         if(nums.length == 0) return 0;
   
5.         if(nums.length == 1) return nums[0];
   
6.         
   
7.         int res = nums[0];
   
8.         int fre = 1;
   
9.         
   
10.         for(int i = 1; i < nums.length; i++){
    
11.             
    
12.             if(nums[i] == res) fre ++;
    
13.             else fre --;
    
14.             
    
15.             if(fre == 0) {
    
16.                
    
17.                 res = nums[i];
    
18.                 fre = 1;
    
19.             }
    
20.         }
    
21.         return res;
    
22.         
    
23.     }
    
24. }

复制代码