###### tags: `Leetcode` `medium` `array` `counting` `python` `c++`

# 229. Majority Element II

## [題目連結:] https://leetcode.com/problems/majority-element-ii/description/

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

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

**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]

## 解題想法:
* 題目為找出數列中出現n/3個以上的數字
* linear time、 O(1) space

* 因為要求線性時間且常數空間:
* 遍歷一次數組判斷
* 因為出現大於n/3次，最終答案也就至多兩個數滿足
* 紀錄兩個: 數字，出現次數
* val1, count1=None, 0
* val2, count2=None, 0
* 遍歷數組:
* 若當前數字==val1:
* count1+=1
* 當前數字==val2:
* count2+=1
* 若有count==0:
* 將該val設為當前數字且其count設為1
* 若皆不屬於且count都還>0:
* count1-=1
* count2-=1
* 判斷最終val1、val2是否符合出現次數大於len(nums)/3

## Python:
* 注意遇到nums=[0,0,0,0] 這種極端case
* 對於計算實際數量方面，不能用nums.count(val)這麼草率

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=[]
        #數字，出現次數
        val1, count1=0, 0
        val2, count2=0, 0
        for num in nums:
            if num==val1:
                count1+=1
            elif num==val2:
                count2+=1
            #若有人count=0: 需要替換且count重設
            elif count1==0:
                val1=num
                count1=1
            elif count2==0:
                val2=num
                count2=1
            #皆不屬於且count都還有扣打
            else:
                count1-=1
                count2-=1
        #計算實際數量
        count1, count2=0, 0
        for num in nums:
            if num==val1:
                count1+=1
            elif num==val2:
                count2+=1
        #判斷最終人選是否>n/3
        if count1>len(nums)//3:
            res.append(val1)
        if count2>len(nums)//3:
            res.append(val2)
        return res

## C++:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int val1=0, count1=0, val2=0, count2=0;
        for (int num: nums){
            if (num==val1)
                count1+=1;
            else if (num==val2)
                count2+=1;
            else if (count1==0)
                val1=num, count1=1;
            else if (count2==0)
                val2=num, count2=1;
            else{
                count1-=1;
                count2-=1;
            }
        }
        //count actually num of val1、val2
        count1=0, count2=0;
        for (int num: nums){
            if (num==val1)
                count1+=1;
            else if (num==val2)
                count2+=1;
        }
        //check more than nums.size()/3 or not
        if (count1>nums.size()/3)
            res.push_back(val1);
        if (count2>nums.size()/3)
            res.push_back(val2);
        return res;
    }
};