# C + +: main elements

2022-05-15 01:06:04

# C++: Main elements

## Problem description

`````` More than half of the elements in an array are called major elements . To give you one   Integers   Array , Find out the main elements . If there is no , return  -1 . Please design the time complexity as  O(N) 、 The space complexity is  O(1)  Solutions for .

Example  1：

Input ：[1,2,5,9,5,9,5,5,5]
Output ：5
Example  2：

Input ：[3,2]
Output ：-1
Example  3：

Input ：[2,2,1,1,1,2,2]
Output ：2
``````

## analysis

1. One of the easiest ways to think of is to use Hash Count the table , Traverse and judge whether the number of occurrences of the current number is greater than half of the length , The time complexity of this method is O（n）, The space complexity is O（n）
2. Notice that the principal element is more than half of the elements , So consider using moor The voting algorithm first finds the number that appears most , Then count its length .

## Realization

``````#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int Moore(vector<int> &nums);
int Hash(vector<int> &nums);
int main()
{

vector<int> nums = {
3,3,4};
//return Hash(nums);
return Moore(nums);
system("pause");
}

int Hash(vector<int>& nums)
{

unordered_map<int,int> cnt;
for(auto& num:nums)
{

if((++cnt[num]) > (nums.size()/2))
return num;
}
return -1;
}

int Moore(vector<int>& nums)
{

int major = -1, cnt = 0;
for(auto& num:nums)
{

if(cnt == 0)
{

major = num;
cnt = 1;
}
else if(major == num)
cnt++;
else
cnt--;
}
for(auto& num:nums)
{

if(major == num)
cnt++;
}
if(cnt > nums.size()/2)
return major;
else
return -1;
}
``````