Liny_@NotePad

沉迷ACG中

求主元素的线性算法

YOYO posted @ 2009年3月12日 21:32 in 【算法】与【数据结构】 with tags 主元素 , 2928 阅读

 知道怎么算，实现起来好囧，百度了一下，发现这个好简洁 = =，不过这个输入时就一定有主元素，故没有再对函数找出来的A[x]作判定：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 100
  5.  
  6. int searchMost(int A[], int n){
  7.         int x = 0;
  8.         for(int i = 1, j = 1; i<n; i++){
  9.                 if(A[x]==A[i]){
  10.                         j++;
  11.                 }else{
  12.                         if(j>0){
  13.                                 j--;
  14.                         }else{
  15.                                 x = i;
  16.                         }
  17.                 }
  18.         }
  19.         return A[x];
  20. }
  21.  
  22. int main(){
  23.         int A[N],n;
  24.  
  25. input:
  26.         cout<<"请输入数组的元素个数（<"<<N<<"）：";
  27.         cin>>n;
  28.  
  29.         if(n<=0){
  30.                 cout<<"n必须大于0！"<<endl;
  31.                 goto input;
  32.         }
  33.         if(n>=N){
  34.                 cout<<"n必须小于"<<N<<"！"<<endl;
  35.                 goto input;
  36.         }
  37.  
  38.         cout<<"请输入数组的元素：";
  39.         for(int i = 0; i<n; i++){
  40.                 cin>>A[i];
  41.         }
  42.  
  43.         cout<<"数组中出现最多的元素是：";
  44.         cout<<searchMost(A,n)<<endl;
  45.  
  46.         return 0;
  47. }

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter