229. Majority Element II

难度: Medium

题目描述

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

 

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

 

Follow up: Could you solve the problem in linear time and in O(1) space?

解题思路

代码实现

解决方案

java

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

        int firstEle = 0;
        int firstCount = 0;
        int secondEle = 0;
        int secondCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (firstCount > 0 && nums[i] == firstEle) {
                firstCount++;
            } else if (secondCount > 0 && nums[i] == secondEle) {
                secondCount++;

            } else if (firstCount == 0) {
                firstEle = nums[i];
                firstCount = 1;
            } else if (secondCount == 0) {
                secondEle = nums[i];
                secondCount = 1;
            } else {
                firstCount--;
                secondCount--;
            }

        }
        int cnt1 = 0;
        int cnt2 = 0;
        for (int d : nums) {
            if (firstCount > 0 && d == firstEle) {
                cnt1++;
            }
            if (secondCount > 0 && d == secondEle) {
                cnt2++;
            }
        }
        List<Integer> ans = new ArrayList<>();
        if (firstCount > 0 && cnt1 > nums.length / 3) {
            ans.add(firstEle);
        }

        if (secondCount > 0 && cnt2 > nums.length / 3) {
            ans.add(secondEle);
        }

        return ans;

    }
}