Moore Voting

1. Majority Element

Given an array of sizen, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

method1: sort and median element is ans!

public class Solution {
    public int majorityElement(int[] nums) {

        int num1 = nums[0], count1 = 0;

        for(int num: nums){

            if(num == num1){
                count1 ++;
            }
            else if(count1 == 0){
                num1 = num;
                count1 = 1;
            }
            else
                count1 --;
        }

        return num1;
    }
}

2. Majority Element II

Given an integer array of size n , find all elements that appear more than⌊ n/3 ⌋times. The algorithm should run in linear time and in O(1) space.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {

        List<Integer> ans = new ArrayList<>();
        if(nums.length == 0) return ans;

        int count1 = 0;
        int count2 = 0;
        int num1 = nums[0];
        int num2 = nums[0];

        for(int num: nums){

            if(num == num1){
                count1++;
            }
            else if(num == num2){
                count2++;
            }
            else if(count1 == 0){
                num1 = num;
                count1 = 1;
            }
            else if(count2 == 0){
                num2 = num;
                count2 = 1;
            }
            else{
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for(int num: nums){
            if(num == num1)
                count1 ++;
            else if(num == num2)
                count2 ++;
        }

        if(count1 > nums.length / 3) ans.add(num1);
        if(count2 > nums.length / 3) ans.add(num2);
        return ans;
    }
}