C/C++教程

C++:主要元素

本文主要是介绍C++:主要元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

C++:主要元素

问题描述

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

 

示例 1:

输入:[1,2,5,9,5,9,5,5,5]
输出:5
示例 2:

输入:[3,2]
输出:-1
示例 3:

输入:[2,2,1,1,1,2,2]
输出:2

分析

  1. 最容易想到的一个方法是使用Hash表进行计数,依次遍历并判断当前数出现的次数是否大于长度的一半,该方法时间复杂度为O(n),空间复杂度为O(n)
  2. 注意到主元是超过一半的元素,因此可以考虑使用moor投票算法先找到出现最多的数,然后再统计其长度。

实现

#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;
}
这篇关于C++:主要元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!