169. Majority Element

169. Majority Element

Question:

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

Thinking:

• Method1:通过hashmap实现，速度较慢

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums .length; i++){
            map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
        }
        int max = 0;
        int result = -1;
        Set<Map.Entry<Integer,Integer>> set = map.entrySet();
        for(Map.Entry<Integer,Integer> entry : set){
            if(entry.getValue() > max){
                result = entry.getKey();
                max = entry.getValue();
            }
        }
        return result;
    }
}

• Method2:先通过排序，再取出中间元素，复杂度为O（lgN）

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

• Method 3: moore’s voting algorithm

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

二刷

还是记得一刷时候的方法三。

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

三刷

1. Redo the method 3 however think in a different way:
   • when we see 2 different numbers, we will remove both of them;
   • when we see 2 same numbers, we will increase the number of appears of current number.
   • the majority number will remove all other numbers and finally leaves as a result;

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