找min和max

看到的貌似是阿里的筆試題，題意是一組數，要找到min和max，同時要求時間復雜度（比較次數）小于2n（2n的辦法都想得到）。

別人的思路：n個數的數組里看作每兩個一組，若n是奇數，最后個單獨看。

然后遍歷一次，找出每組數里的tmax和tmin，tmax存到一個數組，tmin存到一個數組，此時比較次數為n/2;

可知最大數在max數組里,最小數在min數組里,再用普通線性比較分別遍歷兩個數組找到max數組里的最大,min數組里的最小即可比較次數為n/2,n/2

總共為n/2+n/2+n/2=3n/2;再對max和min數組用同樣辦法和直接求無差別。

ps：空間上還可以繼續優化下，維護兩個gmax，gmin，在每次對每組數找tmax和tmin時，tmax直接和gmax比較 tmin和gmin，隨時更新

這樣就不用額外的數組了，或者在原數組里交換位置，讓tmax總在右邊也可..

 1 void fmm(int *arry,int len)
 2 {
 3     int gmax,gmin;
 4     for(int i=0;i<len;i+=2)
 5     {
 6 
 7         int tmax,tmin;
 8         arry[i]>arry[i+1]?tmax=arry[i],tmin=arry[i+1]:tmax=arry[i+1],tmin=arry[i];
 9         if(i==0)
10             gmax=tmax,gmin=tmin;
11         else
12         {
13             gmax=gmax>tmax?gmax:tmax;
14             gmin=gmin<tmin?gmin:tmin;
15         }
16     }
17     
18     if(len%2)
19     {
20         gmax=gmax>arry[len-1]?gmax:arry[len-1];
21         gmin=gmin<arry[len-1]?gmin:arry[len-1];
22     }
23     cout<<gmax<<":"<<gmin<<endl;
24 }

轉載于:https://www.cnblogs.com/cavehubiao/p/3343294.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/377785.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/377785.shtml
英文地址，請注明出處：http://en.pswp.cn/news/377785.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！