All Code in this essay can be found in https://github.com/Vast-Stars/Algorithm/tree/master/Majority

Basic Report

1. Description

Given an array of size n, find the majority element.

The majority element is the element that appears more than ⌊ n/2 ⌋ times.

2. Algorithm

We can use the nature of the problem:

appears more than ⌊ n/2 ⌋ times.

which means we can delete both a and b if a≠b, and this will not change the Majority Element in the remaining part of the array.

Specifically, I use a counter to record the number of occurrences of the target. I initialize target to array[0] , and sequential scan the array sequentially to array[i]. The counter will increase by 1 if array[i]==target, or otherwise will decrease by 1. If counter==0 then pick up next number as new target and continue this process until the entire array is scanned or counter >SIZE/2(which means program find a Majority element clearly).

3. Source Codes

The main function is demonstrated below:

int majorityElement(vector<int>& INPUT) 
{
  int count = 1;
  int target = INPUT[0];
  int size = INPUT.size();
  int total_size = size;
  for (int i = 1; i<total_size && count <= size / 2; i++)
  {
      if (INPUT[i] == target)
          count++;
      else
      {
          count--;
          if (count == 0)
              if (i + 1 ==total_size)
                  return INT_MIN; //Can Not Find Majority Element
              else
              {
                  target = INPUT[i + 1];
                  size = total_size- i - 1;
              }
      }
  }
  return target;
}

Time complexity: O(n) Space complexity: O(1)

This function is tested by LeetCode: 169.Majority Element successfully.

4. Recursive process

graph LR;
  a[*1*,2,3,2,1]--> |Target=1 Counter=1|B[1,*2*,3,2,1] 
  B--> |Target=1 Counter=0|C[1,2,*3*,2,1];
  C--> |Rest Target=3|C;
  C--> |Target=3 Counter=1|D[3,*2*,1];
  D--> |Target=3 Counter=0|E[*1*];
  E--> |Rest Target=1|E;

Further Thinking

1. Algorithm optimization

In fact, we can improve this algorithm in 2 ways.

Use hash . Although it takes O(n) time complexity and O(n) space complexity, hash map(or table) is much convenient to deal with similar problem related statistics.
On the basis of the original algorithm, I change variable size in end condition count <= size / 2. I find that target only needs to be greater than half the length of the remaining array, rather than half the total length. On the implementation, only one additional variable is required to record the last index(i) of target == 0 and use size = total_size- i - 1 instead of size = total_size.

Tested in 15,000 examples(Randomly generated, see source code for details), I get the speed difference between the 2 algorithms:

From the graph we can know it depends on the usage scenarios to choose and optimize algorithm to play its best performance.

2. Similar Problem Ⅰ: Find the Majority Element(appear greater or equal to`⌊ n/2 ⌋` times )

To be honest, it’s confusing me for some time. I consider the cases of the parity of n, or whether there must be a solution to this problem . And it’s very difficult to generalize several cases of the algorithm together.

But later I came across another Majority problem(see blow), and I solved this problem effortlessly.

3. Similar Problem Ⅱ: Find the Majority Element(appear more than `⌊ n/3 ⌋` times )

Problem Source: LeetCode 229. Majority Element II

First of all, we can prove that there is up to 2 majority element . So it is natural to think about using 2 counters to record 2 targets(It seems to “doubled” previous algorithm). What’s differences is we need scan the entire array to count the number of target1 and target2 after the first traversal.

vector<int> majorityElement(vector<int>& nums) 
{
    int t1,t2;
	int c1=0,c2=0;
	vector<int> ans;
	for(int i:nums)
	{
		if(i==t1 || i==t2)
		{
			if(i==t2)
				c2++;
			else
				c1++;
		}
		else 
		{
			if(c1==0)
			{
				t1=i;
				c1=1;
			}
			else if(c2==0)
			{
				t2=i;
				c2=1;
			}
			else
				c1--;c2--;
		}
	}
	c1=0;c2=0;
	for(int i:nums)
	{
		if(i==t1) c1++;
		if(i==t2) c2++;
	}
	if(c1>nums.size()/3)
		ans.push_back(t1);
	if(c2>nums.size()/3)
		ans.push_back(t2);	
	return ans;
}