无序数组中求最大值和最小值的最少比较次数
无序数组中求最大值和最小值的最少比较次数
原理介绍
求一个无序数组中的最大值和最小值是一个很常见的情况, 一般来说, 最大值和最小值不是同一个元素, 我们可以通过下面几种方法来求:
- 排序算法:将数组排序后, 第一个元素是最小值,最后一个元素是最大值,以快排平均复杂度为例,时间复杂度 $O(NlogN)$,空间复杂度: $O(logN)$,比较次数: $NlogN$ ;
- 两个元素记录最大值和最小值,判断每个值是否大于最大值或者最小值, 比较次数: $2*N$';
- 使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数: $1.5*N$
- 将相邻的数进行比较,大的放在偶数位置,小的放在奇数位置, 最后奇数位置比较和偶数位置对应比较,得到最大值和最小值,比较次数: $1.5*N$ ;
- 分治法, topK 问题的简化版本分成两部分,找到前半部分的 Min Max, 最后比较结果可得到最后的值
方法3 和方法4的 过程很接近, 方法3 更为容易实现, 具体实现可见后续
算法实现
方法1 快排
// 找到数组元素的最大值和最小值
vector<int> findMinMax(vector<int> arr)
{
sort(arr.begin(),arr.end());
return {arr[0],arr.back()};
}方法 2
// 找到数组元素的最大值和最小值
vector<int> findMinMax(vector<int> arr)
{
int min_ = INT_MAX,max_ = INT_MIN;
for(int i=0;i<arr.size();++i)
{
if(arr[i] > max_)
max_ = arr[i];
if(arr[i] < min_)
min_ = arr[i];
}
return {min_,max_};
}方法 3
使用两个值记录最大值和最小值, 每次取出两个值,先进行比较,小的与最小值比较,大的与最大值比较 , 比较次数: $1.5*N$
// 找到数组元素的最大值和最小值
vector<int> findMinMax(vector<int> arr) {
int min_ = INT_MAX,max_ = INT_MIN;
// 处理前面偶数个元素
for(int i=0;i<arr.size()/2;++i) {
// 得到两个元素的最大值和最小值
int tmp_min,tmp_max;
if(arr[i] < arr[i+1]) {
tmp_min = arr[i];
tmp_max = arr[i+1];
} else {
tmp_min = arr[i+1];
tmp_max = arr[i];
}
// 比较,更新最大值和最小值
if(tmp_max > max_) max_ = tmp_max;
if(tmp_min < min_) min_ = tmp_min;
}
// 处理数组个数为奇数的情况 // 处理最后一个元素
if(arr.size()%2) {
int tmp = arr.back();
if(tmp > max_) max_ = tmp;
if(tmp < min_) min_ = tmp;
}
return {min_,max_};
}方法 4
比较前面偶数个元素,小的放在奇数位置,大的放在偶数位置, 比较次数: $1.5*N$
// 找到数组元素的最大值和最小值
vector<int> findMinMax(vector<int> arr) {
int min_ = INT_MAX,max_ = INT_MIN;
// 调整位置, 小的位于奇数,大的位置偶数
for(int i=0;i<arr.size()/2;i++) {
if(arr[i] > arr[i+1]) swap(arr[i],arr[i+1]);
}
// 更新最大值和最小值
for(int i=0;i<arr.size()/2;i++) {
if(arr[i] < min_) min_ = arr[i];
if(arr[i+1] > max_) max_ = arr[i+1];
}
// 处理数组个数为奇数的情况 // 处理最后一个元素
if(arr.size()%2) {
int tmp = arr.back();
if(tmp > max_) max_ = tmp;
if(tmp < min_) min_ = tmp;
}
return {min_,max_};
}方法5
在N个数中求最小值Min和Max, 分成两个部分,依次取Min和Max,
略