LeetCode Q169: Majority Element

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

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

Solution 1:
Using hash table:

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	unordered_map<int, int> myMap;
	for(int i=0; i<nums.size(); i++){
	myMap[nums[i]]=myMap[nums[i]]+1;
	if(myMap[nums[i]]>int(nums.size())/2)
	return nums[i];
	}
	}
	};

view raw Q169MajorityElement.cpp hosted with ❤ by GitHub

Solution 2:

	public class Solution {
	public int majorityElement(int[] num) {
	int major=num[0], count = 1;
	for(int i=1; i<num.length;i++){
	if(count==0){
	count++;
	major=num[i];
	}else if(major==num[i]){
	count++;
	}else count--;
	}
	return major;
	}
	}

view raw Q169-2.cpp hosted with ❤ by GitHub

Actually there are many other solutoins, please see: Here

Round 2 solution:

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int cnt=1;
	int num=nums[0];
	for(int i=1; i<nums.size(); i++){
	if(nums[i]==num)
	cnt++;
	else
	if(--cnt==0){
	num=nums[i];
	cnt=1;
	}
	}
	return num;
	}
	};

view raw Q169Rnd2.cpp hosted with ❤ by GitHub