169. Majority Element.md

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;
    }
}

Fourth time

• Method 1: Moore's Algorithm

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