隨筆-28  評論-51  文章-10  trackbacks-0
          用遞歸法(尾遞歸)求最多元素,即找出出現(xiàn)次數(shù)大于n/2的元素
          基于原理:去掉兩個不同的元素,剩下數(shù)組里的最多元素仍然是整個數(shù)組的最多元素(如果存在的話)

           1 #include <stdio.h>
           2 int majority(int [], int,int );
           3 
           4 int main()
           5 {
           6     int i = 0;
           7     int c = 0;
           8     int data [] = {3,5,5,2,2,2,2};
           9     int maj = majority(data,1 ,7);
          10     for( ; i < 7; i++)
          11     {
          12         if(maj == data[i])
          13            c++;
          14     }    
          15     printf("The majority num of this array is: %d\n", c>3?maj:-1);
          16     return 0;
          17 }
          18 /*s for the begining index, and e for the ending index
          19 * * find the cadidate num of majority*/
          20 int majority(int data[], int s, int e)//begin s = 1, e = n(including)
          21 {
          22     int c = 1;// count the candidate majority num
          23     int j; //fot the index move on
          24     int i = 0;
          25     for( j = s; j< e; j++)
          26     {
          27         if( data[s-1== data[j])
          28             c++;
          29         else
          30         {
          31             if(--c==0)
          32             break;    
          33         }        
          34     }    
          35     if(c>0)
          36         return data[s-1];
          37     else
          38          majority(data, j+1, e);
          39             
          40 }


          posted on 2008-03-29 23:03 fullfocus 閱讀(542) 評論(1)  編輯  收藏 所屬分類: 算法

          評論:
          # re: 求多數(shù)元素 2008-09-27 09:53 | 冶人
          品讀了
          Thx!
          如果我想實現(xiàn)求多數(shù)元素,但時間復(fù)雜度為O(n),其它無限制,該如何實現(xiàn)呢?請教!  回復(fù)  更多評論
            
          主站蜘蛛池模板: 桑日县| 阳原县| 霍邱县| 石渠县| 洪洞县| 鹤庆县| 泾源县| 屏东县| 定西市| 阳谷县| 鸡泽县| 上虞市| 五指山市| 托克托县| 沂南县| 马关县| 泸西县| 社会| 三都| 陇西县| 航空| 凯里市| 夹江县| 云梦县| 通许县| 湖北省| 从江县| 江都市| 乾安县| 蒲城县| 百色市| 稷山县| 北流市| 探索| 五莲县| 塘沽区| 上杭县| 类乌齐县| 垣曲县| 望奎县| 黄冈市|