current position:Home>C + +: main elements

C + +: main elements

2022-05-15 01:06:04Hua Luoxi

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;
}

copyright notice
author[Hua Luoxi],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/132/202205120549039710.html

Random recommended