给定一个数组，找到多数元素，C ++解决方案

多数元素是重复一半以上的元素。

Example:
[1, 2, 3, 4, 4, 4, 4, 4, 5]
Output: 4

元素总数为9，并且将4重复5次。它已经重复了一半以上的时间。

我们可以通过使用 摩尔投票算法。如果存在多数元素，则此算法将起作用。如果没有多数元素，您将得到错误的结果。

以下是该算法的工作原理：

1. 将第一个元素视为most_element，并使用count变量在每次遇到该变量时递增。
2. 如果当前索引处的变量与major_element不同，则递减计数器。
3. 如果计数器为0，则将当前元素视为多数元素，然后继续遍历数组。
4. 最后，结果保存在“ majority_element”中。
5. 这也将适用于未排序的数组。

在解决方案中，我给出了调试语句，以便您可以了解确切的流程。

C ++解决方案

#include<iostream>
#include<vector>
#include<string.h>

using namespace std;

int majority_element_moore_voting_algorithm(vector<int> &num) 
{

	int major=num[0];
	int count = 1;

	cout<<"============start debugging============"<<endl;
	cout<<"Step 1: majority element = "<<major<<" count = "<<count<<endl;
	for(int i=1; i<num.size();i++)
	{
	cout<<"Step 2: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;

		if(count==0)
		{

			count++;
			major=num[i];
	cout<<"Step 3: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;

		}
		else if(major==num[i])
		{
			count++;
	cout<<"Step 4: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;

		}
		else
		{ 
			count--;
	cout<<"Step 5: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;

		}
	}

	cout<<"============end debugging============"<<endl;

	return major;
}



int main()
{
	vector<int> number = {1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6};
	int majority_element = majority_element_moore_voting_algorithm(number);
	cout<<"The majority element is "<<majority_element<<endl;

	return 0;
}

输出：

============start debugging============

Step 1: majority element = 1 count = 1

Step 2: majority element = 1 count = 1 num = 2

Step 5: majority element = 1 count = 0 num = 2

Step 2: majority element = 1 count = 0 num = 3

Step 3: majority element = 3 count = 1 num = 3

Step 2: majority element = 3 count = 1 num = 4

Step 5: majority element = 3 count = 0 num = 4

Step 2: majority element = 3 count = 0 num = 5

Step 3: majority element = 5 count = 1 num = 5

Step 2: majority element = 5 count = 1 num = 5

Step 4: majority element = 5 count = 2 num = 5

Step 2: majority element = 5 count = 2 num = 5

Step 4: majority element = 5 count = 3 num = 5

Step 2: majority element = 5 count = 3 num = 5

Step 4: majority element = 5 count = 4 num = 5

Step 2: majority element = 5 count = 4 num = 5

Step 4: majority element = 5 count = 5 num = 5

Step 2: majority element = 5 count = 5 num = 5

Step 4: majority element = 5 count = 6 num = 5

Step 2: majority element = 5 count = 6 num = 6

Step 5: majority element = 5 count = 5 num = 6

============end debugging============

The majority element is 5

该网站上可用的教程列表：