博客

今天在做leetcode 169题，求众数

该题定义的众数是出现次数大于n/2次，实际求中位数即可。

• 问题来了：如何通过c++求解真正的众数呢？即就是数组中出现次数最多的数。
  

下面给出解法：

1.当数组大小为1，输出arr[0]即可；

2.数组大小为2，如果相等，输出arr[0];反之输出arr[0],arr[1];

3.数组大小大于2时：

1）将数组从小到大排列；

2）将数组去重并统计每个数字出现次数；

3）求出最大的次数；

4）输出最大次数对应的数字（可能不止一个）；

代码如下：

#include "iostream"
#include "stdlib.h"
#include <vector>
#include <algorithm>

using namespace std;

/************ 求数组中的众数 *************/
vector<int> majorityElement(vector<int> arr) {
	
	vector<int> numSet;
	vector<int> count;
	vector<int> res;
	numSet.push_back(arr[0]);
	count.push_back(1);
	/*if (arr.size() < 1)
	{
		res.push_back([]);
		return;
	}//return NULL;
	else */if (arr.size() == 1)
	{
		res.push_back(arr[0]);
		return res;
	}//当数组大小为1时
	else if (arr.size() == 2)
	{
		res.push_back(arr[0]);
		if (arr[0] != arr[1])
		{
			res.push_back(arr[1]);
		}
		return res;
	} //当数组大小为2时

	//当数组大小大于等于三时
	sort(arr.begin(), arr.end()); //先排序

	int m = 0;
	for (int i = 1; i < arr.size(); i++)
	{
		if (arr[i] != arr[i - 1]) {
			numSet.push_back(arr[i]);//记录下不重复的值
			count.push_back(1); //并将次数赋值为1
			m++;
		}
		else
			count[m]++; //当和前值相等时，次数加1
	}
	int max = count[0];
	for (int i = 0; i < count.size(); i++) //求出最大的次数
	{
		if (max < count[i])
			max = count[i];
	}
	for (int i = 0; i < count.size(); i++) //输出次数最大的值
	{
		if (count[i] == max)
			res.push_back(numSet[i]);
	}
	return res;
		//cout << arr[i] << ' ';
}

int main()
{
	vector <int> arr = {12, 2, 5, 6, 21};//{ 1, 2, 2, 2, 4, 6, 6, 8, 11 };
	vector<int> res;
	res = majorityElement(arr);

	for (int i = 0; i < res.size(); i++)
	{
		cout << res[i] << ' ';
	}
	
	system("pause");
	return 0;