平邑网站定制,win7电脑做网站服务器,济南建设银行,苏州制作网页方案看到的貌似是阿里的笔试题#xff0c;题意是一组数#xff0c;要找到min和max#xff0c;同时要求时间复杂度#xff08;比较次数#xff09;小于2n#xff08;2n的办法都想得到#xff09;。 别人的思路#xff1a;n个数的数组里看作每两个一组#xff0c;若n是奇数题意是一组数要找到min和max同时要求时间复杂度比较次数小于2n2n的办法都想得到。 别人的思路n个数的数组里看作每两个一组若n是奇数最后个单独看。 然后遍历一次找出每组数里的tmax和tmintmax存到一个数组tmin存到一个数组此时比较次数为n/2; 可知最大数在max数组里,最小数在min数组里,再用普通线性比较分别遍历两个数组 找到max数组里的最大,min数组里的最小即可比较次数为n/2,n/2 总共为n/2n/2n/23n/2;再对max和min数组用同样办法和直接求无差别。 ps空间上还可以继续优化下维护两个gmaxgmin在每次对每组数找tmax和tmin时tmax直接和gmax比较 tmin和gmin随时更新 这样就不用额外的数组了或者在原数组里交换位置让tmax总在右边也可.. 1 void fmm(int *arry,int len)2 {3 int gmax,gmin;4 for(int i0;ilen;i2)5 {6 7 int tmax,tmin;8 arry[i]arry[i1]?tmaxarry[i],tminarry[i1]:tmaxarry[i1],tminarry[i];9 if(i0)
10 gmaxtmax,gmintmin;
11 else
12 {
13 gmaxgmaxtmax?gmax:tmax;
14 gmingmintmin?gmin:tmin;
15 }
16 }
17
18 if(len%2)
19 {
20 gmaxgmaxarry[len-1]?gmax:arry[len-1];
21 gmingminarry[len-1]?gmin:arry[len-1];
22 }
23 coutgmax:gminendl;
24 } 转载于:https://www.cnblogs.com/cavehubiao/p/3343294.html
