中科院的一道面试题，求大家给个标准的答案啊多谢
中科院的一道面试题，求大家给个标准的答案啊！！谢谢设有n个不同的元素存于顺序结构中，试问：用少于2n-3的比
中科院的一道面试题，求大家给个标准的答案啊！！谢谢
设有n个不同的元素存于顺序结构中，试问：用少于2n-3的比较次数选出这n个元素的最大值和最小值。
[解决办法]
每次取两个数，比较二者，再把大的和max比，小的和min比。
这样是3n/2的复杂度
[解决办法]
楼上的是一种办法，你还可以用随机求第k 大的算法来求
[解决办法]
也可以采用二分法
pair<int,int> findMaxMin(int a[], int n)
{
if(n == 2){
if(a[0] < a[1]) return make_pair(a[1],a[0]);
else return make_pair(a[0],a[1]);
}
if(n == 1) return make_pair(a[0],a[0]);
pair<int,int> leftMaxMin, rightMaxMin;
leftMaxMin = find(a, n>>1);
rightMaxMin = find(a+(n>>1), n-(n>>1));
return make_pair(leftMaxMin.first > rightMaxMin.first ?
leftMaxMin.first : rightMaxMin.first ,
leftMaxMin.second < rightMaxMin.second ?
leftMaxMin.second : rightMaxMin.second);
}
则在一次的findMaxMin调用中，最多比较四次，即
（1）if(n == 1)
（2）if(n == 2)
（3）leftMaxMin.first > rightMaxMin.first ? leftMaxMin.first : rightMaxMin.first
（4）leftMaxMin.second < rightMaxMin.second ? leftMaxMin.second : rightMaxMin.second
另一方面，由于二分，findMaxMin的调用次数为O(log2(n))，则总的比较次数O(4log2(n))
[解决办法]好吧，我真是2到家了，请无视ls的回复！
