Question

Formatted question description: https://leetcode.ca/all/229.html

 229. Majority Element II

 Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

 Note: The algorithm should run in linear time and in O(1) space.

 Example 1:

 Input: [3,2,3]
 Output: [3]
 Example 2:

 Input: [1,1,1,3,3,2,2,2]
 Output: [1,2]

 @tag-array

Algorithm

Moore voting algorithm

The core is to fight against consumption. To play a game of lords fighting for hegemony, suppose your population exceeds more than half of the total population, and it can be guaranteed that every population can go out to fight and die together.

In the end, the country where people survive is victory.

Then there is a big mess, everyone at the worst will unite against you (corresponding to the mode every time you choose as a counter), Or other countries will also attack each other (other numbers will be selected as counter numbers),

But as long as you don’t fight internally, you will definitely win in the end. The last thing left must be your own.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Majority_Element_II {

    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
            List<Integer> result = new ArrayList<Integer>();

            if (nums == null || nums.length == 0) {
                return result;
            }

            if (nums.length == 1) {
                result.add(nums[0]);
                return result;
            }

            // at most there are 2 candidates
            int candidate1 = nums[0];
            int candidate2 = 0;

            int count1 = 1;
            int count2 = 0;

            // eg Input: [1,3,3,2,2, 1,1,2]
            for (int i = 1; i < nums.length; i++) {
                int num = nums[i];
                if (candidate1 == num) {
                    count1++;
                } else if (candidate2 == num) {
                    count2++;
                } else if (count1 == 0) {
                    candidate1 = num;
                    count1 = 1;
                } else if (count2 == 0) {
                    candidate2 = num;
                    count2 = 1;
                } else {
                    count1--; // @note: here is actually -1 for candidate-1, candidate-2, and nums[i]
                    count2--; //        consumption competing
                }
            }

            count1 = 0;
            count2 = 0;

            for (int num : nums) {
                if (num == candidate1) {
                    count1++;
                } else if (num == candidate2) {
                    count2++;
                }
            }

            if (count1 > nums.length / 3) {
                result.add(candidate1);
            }

            if (count2 > nums.length / 3) {
                result.add(candidate2);
            }

            return result;
        }
    }
}

All Problems

All Solutions