数组之求无序数组中的min和max

//数组之求无序数组中的min和max //方法一：看作两个问题，分别找出min和max，需要遍历数组两次，比较次数为2N; void getMaxAndMin(int *nums,int len,int &max,int &min) { if(nums==nullptr||len<=0) return; max=nums[0]; min=nums[0]; for(int i=0;i<len;++i) { if(max<nums[i]) max=nums[i]; } for(int j=0;j<len;++j) { if(min>nums[j]) min=nums[j]; } } int main() { int nums[]={2,4,5,6,3,7,8,9,10,11}; int len=(sizeof(nums)/sizeof(nums[0])); int min; int max; getMaxAndMin(nums,len,max,min); cout<<min<<endl; cout<<max<<endl; system("pause"); return 0; } //方法二：用两个变量分别标记目前已找到的min和max；每次取出一个元素，先与已找到的min比较， // 再与已找到的max比较;此方法需要遍历数组1次，比较次数为2N; void getMaxAndMin(int *nums,int len,int &max,int &min) { if(nums==nullptr||len<=0) return; max=nums[0]; min=nums[0]; for(int i=0;i<len;++i) { if(max<nums[i]) max=nums[i]; if(min>nums[i]) min=nums[i]; } } //方法三：维持两个变量分别标记min和max，每次比较相邻两个数，较大者与max比较，较小者与min进行比较难； // 只需遍历数组一次，比较次数为1.5N； void getMaxAndMin(int *nums,int len,int &max,int &min) { if(nums==nullptr||len<=0) return ; max=nums[0]; min=nums[0]; for(int i=1;i<len-1;i+=2) { if(nums[i+1]==NULL) { if(nums[i]>max) max=nums[i]; if(nums[i]<min) min=nums[i]; } if(nums[i]>nums[i+1]) { if(nums[i]>max) max=nums[i]; if(nums[i+1]<min) min=nums[i+1]; } else { if(nums[i+1]>max) max=nums[i+1]; if(nums[i]<min) min=nums[i]; } } } //方法四：分治法；将数组划分成两半，分别找出两边的max和min；则数组的max和min分别是两个边最小者的较小者，最大者的较大者； // 只需遍历数组一次，比较次数为1.5N； #include<iostream> using namespace std; void getMaxAndMin(int *nums,int start,int end,int &max,int &min) { int max1=nums[0],min1=nums[0],max2=nums[0],min2=nums[0]; if(end-start==1||end-start==0) { nums[start]>nums[end]?(max=nums[start],min=nums[end]):(max=nums[end],min=nums[start]); } else { int k=(start+end)/2; getMaxAndMin(nums,start,k,max1,min1); getMaxAndMin(nums,k+1,end,max2,min2); max=max1>max2?max1:max2; min=min1<min2?min1:min2; } } int main() { int nums[]={4,5,6,2,7,17,9,10,19,16}; int len=(sizeof(nums)/sizeof(nums[0])); int min; int max; getMaxAndMin(nums,0,len-1,max,min); cout<<min<<endl; cout<<max<<endl; system("pause"); return 0; }