求解数组中的主元素

曾经终败给现在 2021-12-12 02:15 258阅读 0赞

原题：《数据结构与算法分析C++描述（第三版）》练习2.26

问题描述：大小为N的数组的主元素是出现次数超过N/2的元素。找到给定数组的主元素，若没有，应指出。

完整代码：

1 #include<iostream>
     2 #include<vector>
     3 
     4 using namespace std;
     5 
     6 void cand(vector<int> &v)
     7 {
     8     vector<int>::iterator itf = v.begin();
     9     vector<int>::iterator ite = v.begin();
    10     while(itf!=v.end()&&ite!=v.end())
    11     {
    12         if(*itf==*ite)
    13         {
    14             itf=v.erase(ite);
    15             ite=itf+1;
    16         }
    17         else
    18         {
    19             itf=v.erase(itf,ite);
    20             ite=itf+1;
    21         }
    22     }
    23     if(itf!=v.end()&&v.size()>1) v.erase(itf);
    24     if(v.size()>2) cand(v);
    25 }
    26 int mainem(vector<int> v)
    27 {
    28     int len=v.size();
    29     vector<int> v1(v);
    30     cand(v1);
    31     int len1=v1.size();
    32     int count;
    33     if(len1>0)
    34     {
    35         for(int i=0;i<len1;i++)
    36         {
    37             count=0;
    38             for(int j=0;j<len;j++)
    39             {
    40                 if(v[j]==v1[i]) count++;
    41             }
    42             if(count>len/2) return v1[i];
    43         }
    44     }
    45     if(len%2==1)
    46     {
    47         count=0;
    48         for(int i=0;i<len;i++)
    49         {
    50             if(v[i]==v[len-1]) count++;
    51         }
    52         if(count>len/2) return v[len-1];
    53     }
    54     return -1;
    55 }
    56 
    57 int main()
    58 {
    59     int x;
    60     vector<int> v;
    61     while(cin>>x)
    62         v.push_back(x);
    63     int result=mainem(v);
    64     if(result>0)     cout<<"main element:"<<result<<endl;
    65     else cout<<"no main element"<<endl;
    66     return 0;
    67 }

注：为方便，将未找到主元素的返回值设为-1，所以测试使用正数数组。

转载于:https://www.cnblogs.com/moren/p/3659668.html