169. Majority Element.md

169. Majority Element

---

Difficulty : Easy

Related Topics : Array、Divide and Conquer、Bit Manipulation

---

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

---

Solution

• mine
  • Java
    • Runtime: 9 ms, faster than 40.01%, Memory Usage: 44.4 MB, less than 54.64% of Java online submissions

    // O(N)time
    // O(N)space
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int t = nums[i];
            if(map.containsKey(t)){
                map.put(t, map.get(t) + 1);
            }else{
                map.put(t,1);
            }
        }
        for(Integer i : map.keySet()){
            if(map.get(i) > nums.length / 2){
                return i;
            }
        }
        return 0;
    }
    

---

• the most votes

• Boyer-Moore Voting Algorithm Runtime: 1 ms, faster than 99.93%, Memory Usage: 42.8 MB, less than 79.18% of Java online submissions

  // O(N)time
  // O(1)space
  public int majorityElement(int[] num) {
      int major=num[0], count = 1;
      for(int i=1; i<num.length;i++){
          if(count==0){
              count++;
              major=num[i];
          }else if(major==num[i]){
              count++;
          }else count--;
  
      }
      return major;
  }
  

• Arrays.sort Runtime: 1 ms, faster than 99.93%, Memory Usage: 42.9 MB, less than 71.70% of Java online submissions

  //O(N * logN)time
  //O(1) or O(N)space
  public int majorityElement(int[] nums) {
      Arrays.sort(nums);
      return nums[nums.length/2];
  }
  

• more solution

---