（数组）众数问题-白红宇

（数组）众数问题

阅读量：6264 次

发布时间：2019-06-22

本文共 1035 字，大约阅读时间需要 3 分钟。

题目：

给一数组，如果存在众数，找出众数，即超过一半的数，如果不存在，返回-1.

思路：

众数：众数出现的次数大于其他所有数出现次数之和

方法1：hashmap

通过遍历数组，将数组每个数都通过hashmap来统计其出现的个数，如果某个数个数超过一半，则为众数。

时间空间复杂度均为O(n)

方法2：Moore Voting Algorithm

众数存在的情况下，每次扔掉两个不同的数，众数不变，最终剩下的数一定是众数。

扔掉一个众数和一个非众数，众数不变

扔掉两个非众数，众数不变

时间复杂度O(n)，空间复杂度O(1)

代码：

#include 
     
      #include 
      
       #include 
       #include 
        
         using namespace std;class Solution {public:    // hash_map method    int majorityElement1(vector
         
           &num) {        int n =num.size();        if(n==1) return num[0];        map
          
            m; for(vector
           
            ::iterator it=num.begin();it!=num.end();it++){ m[*it]+=1; if(m[*it] > floor(n/2)) return *it; } return -1; } // moore voting algorithm int majorityElement2(vector
            
              &num){ int n=num.size(); if(n==1) return num[0]; int count=0; int x; for(int i=0;i
             
              floor(n/2)) return x; else return -1; }};int main(){ int A[]={ 2,3,4,5,2,6,2}; int n=sizeof(A)/sizeof(A[0]); vector
              
                nums(A,A+n); Solution s; cout<
               
                <