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

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5 * 104
	-109 &lt;= nums[i] &lt;= 109


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

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        
        #Boyer Moore Voting Algo (As used in ME1 ques) 
        #now we can observe that there cannot be more than two elements occuring more than n//3 times in an array
        #so find two majority elements(me=majority element)
        

        n=len(nums)
        req=n//3  #for an element to be ME required number of times present 

        c1=0 #count 1
        c2=0 #count 2
        me1=None #majority element 1
        me2=None #majority element 2

        for i in nums:
            if i == me1:
                c1+=1

            elif i == me2:
                c2+=1

            elif c1 == 0:
                me1=i
                c1=1

            elif c2 == 0:
                me2=i
                c2=1

            else:
                c1-=1
                c2-=1
        #here we have found our majority elements now check if the found majority element is ME
        # print(me1,me2)

        #check if the found majority element is ME
        c1=0
        c2=0
        for i in nums:
            if i==me1:
                c1+=1
            if i==me2:
                c2+=1
        # print(c1,c2)

        if c1 > req  and c2 > req:

            return [me1,me2]

        elif c1> req :
            return [me1]

        elif c2> req :
            return [me2]
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int val1 = nums[0], val2 = nums[0], cnt1 = 1, cnt2 = 0;
        for(int i = 1; i < nums.length; i++){
            if(val1 == nums[i]){
                cnt1++;
            } else if(val2 == nums[i]){
                cnt2++;
            } else{
                if(cnt1 == 0){
                    val1 = nums[i];
                    cnt1++;
                } else if(cnt2 == 0){
                    val2 = nums[i];
                    cnt2++;
                } else{
                    cnt1--;
                    cnt2--;
                }
            }
        }
        int check1 = 0, check2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(val1 == nums[i])check1++;
            else if(val2 == nums[i])check2++;
        }
        List<Integer> ans = new ArrayList<>();
        if(check1 > nums.length / 3) ans.add(val1);
        if(check2 > nums.length / 3) ans.add(val2);
        return ans;
    }
}
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {

        int n = nums.size();

        vector<int> result;

        int num1 = -1 , num2 = -1 , count1 = 0 , count2 = 0;

        for(auto it : nums){

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

        }

        count1 = 0;
        count2 = 0;

        for(auto it : nums){

            if(it == num1) ++count1;
            else if(it == num2) ++count2;

        }

        if(count1>(n/3)) result.push_back(num1);
        if(count2>(n/3)) result.push_back(num2);

        return result;

    }
};
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    const objElement = {};
    const timesVar = Math.floor(nums.length/3);
    const resultSet = new Set();

    for(var indexI=0; indexI<nums.length; indexI++){
       if(objElement[nums[indexI]]) {
               objElement[nums[indexI]] = objElement[nums[indexI]] + 1;
        }
       else objElement[nums[indexI]] = 1;

       if(objElement[nums[indexI]]>timesVar) resultSet.add(nums[indexI]);
    }

    return [...resultSet];
};
Majority Element II