原题链接在这里：

题目：

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.

题解：

Method 1：最容易想到的就是用HashMap 计数，数值大于n/2(注意不是大于等于而是大于)，就是返回值。Time Complexity: O(n). Space: O(n).

Method 2: 用sort, 返回sort后array的中值即可. Time Complexity: O(n*logn). Space: O(1).

Method 3: 维护个最常出现值，遇到相同count++, 遇到不同count--, count为0时直接更改最常出现值为nums[i]. Time Complexity: O(n). Space: O(1).

AC Java:

1 public class Solution { 2     public int majorityElement(int[] nums) { 3         /* 4         //Method 1, HashMap 5         HashMap
     
       map = new HashMap<>(); 6         for(int i = 0;i
      
        it = map.keySet().iterator(); //Iterate HashMap15         while(it.hasNext()){16             int keyVal = it.next();17             //There is an error here: Pay attentation, it is ">", but not ">="18             //If we have three variables [3,2,3], ">=" will also return 2, 1>=3/219             if(map.get(keyVal) > nums.length/2){20                 return keyVal;21             }22         }23         24         return Integer.MIN_VALUE;25         */26         27         /*Method 2, shortcut28         Arrays.sort(nums);29         return nums[nums.length/2];30         */31         32         //Method 333         if(nums == null || nums.length == 0)34             return Integer.MAX_VALUE;35         int res = nums[0];36         int count = 1;37         for(int i = 1; i< nums.length; i++){38             if(res == nums[i]){39                 count++;40             }else if(count == 0){41                 res = nums[i];42                 count = 1;43             }else{44                 count--;45             }46         }47         return res;48         49     }50 }
      
     

跟上.