struct Pair
{
int min;
int max;
};
struct Pair getMinMax(int arr[], int n)
{
struct Pair minmax;
int i;
// If array has even number of elements
// then initialize the first two elements
// as minimum and maximum
if (n % 2 == 0)
{
if (arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.min = arr[0];
minmax.max = arr[1];
}
// Set the starting index for loop
i = 2;
}
// If array has odd number of elements
// then initialize the first element as
// minimum and maximum
else
{
minmax.min = arr[0];
minmax.max = arr[0];
// Set the starting index for loop
i = 1;
}
// In the while loop, pick elements in
// pair and compare the pair with max
// and min so far
while (i < n - 1)
{
if (arr[i] > arr[i + 1])
{
if(arr[i] > minmax.max)
minmax.max = arr[i];
if(arr[i + 1] < minmax.min)
minmax.min = arr[i + 1];
}
else
{
if (arr[i + 1] > minmax.max)
minmax.max = arr[i + 1];
if (arr[i] < minmax.min)
minmax.min = arr[i];
}
// Increment the index by 2 as
// two elements are processed in loop
i += 2;
}
return minmax;
}
// Driver code
int main()
{
int arr[] = { 1000, 11, 445,
1, 330, 3000 };
int arr_size = 6;
Pair minmax = getMinMax(arr, arr_size);
cout << "nMinimum element is "
<< minmax.min << endl;
cout << "nMaximum element is "
<< minmax.max;
return 0;
}
在这个qsn中，我们必须同时返回最大值和最小值，所以这里构造了结构体。我从GEEKSFORGEEKS网站复制了这段代码。我正在尝试这个代码的方法，但怀疑这里的比较是如何计算的。在这段代码中，我想知道如何比较是3*(n-1)/2当n=奇数?
以上代码就是过早优化的定义。下面的代码每两个元素进行4次int比较，减少到3次，这使得代码难以阅读，更容易编写bug。
即使在下面编写的代码中，也可以将它们更改为if() else if()，因为它们使用相同的初始值填充，因此两个条件都不可能为真。但是，为了让读者思考这是不是真的，做这样的改变是不值得的。
试图变得太聪明，你只会比自己聪明。
struct Pair
{
int min;
int max;
};
Pair getMinMax(int arr[], int length){
Pair output = {0, 0};
if(length < 1){
return output;
}
output.min = arr[0];
output.max = arr[0];
for(int i= 1; i < length; i++){
if(arr[i] < output.min){
output.min = arr[i];
}
if(arr[i] > output.max){
output.max = arr[i];
}
}
return output;
}
int main()
{
int array[] = { 8, 6, 4, 2, 9, 4};
auto data = getMinMax(array, 6);
std::cout << data.min << " " << data.max;
}
使用STL代码(c++ 20)解决方案:
#include <algorithm>
#include <vector>
#include <iostream>
struct MinMaxResult
{
int min;
int max;
};
MinMaxResult getMinMax(const std::vector<int>& values)
{
return (values.size() == 0) ?
MinMaxResult{} :
MinMaxResult(std::ranges::min(values), std::ranges::max(values));
}
int main()
{
std::vector<int> values{ 8, 6, 4, 2, 9, 4 };
auto data = getMinMax(values);
std::cout << data.min << ", " << data.max;
return 0;
}
有答案(我认为很好)，但到目前为止，没有一个真正计算比较的次数。对于std::minmax_element，您可以像这样计算比较的次数:
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
template <typename TAG>
struct compare {
static size_t count;
template <typename T>
bool operator()(const T& a,const T& b){
++count;
return a < b;
}
};
template <typename TAG> size_t compare<TAG>::count = 0;
template <typename TAG>
compare<TAG> make_tagged_compare(TAG) { return {};}
int main()
{
std::vector<int> x{1,2,3};
auto c = make_tagged_compare([](){});
auto mm = std::minmax_element(x.begin(),x.end(),c);
std::cout << *mm.first << " " << *mm.second << " " << c.count;
}
标准算法可以复制传递给它们的谓词，因此count是static。因为以后我想重用compare来计算不同的算法，所以我对它进行了标记(每个lambda表达式的类型不同，因此可以用作唯一标记)。输出为:
1 3 3
它正确地找到最小和最大，1和3，并且需要3次比较才能实现。
现在，如果你想将它与不同的算法进行比较，它看起来与上面的非常相似。传递一个函子，用于比较元素并计算算法的比较次数。例如，我使用一个骨架实现，它只进行一次比较，并返回{x[0],x[1]}或{x[1],x[0]}:
template <typename IT, typename Compare>
auto dummy_minmax(IT first, IT last,Compare c) {
auto second = first+1;
if (c(*first,*second)) return std::pair(*first,*second);
else return std::pair(*second,*first);
}
int main()
{
std::vector<int> x{1,2,3};
auto c = make_tagged_compare([](){});
auto mm = std::minmax_element(x.begin(),x.end(),c);
std::cout << *mm.first << " " << *mm.second << " " << c.count << "n";
double x2[] = {1.0,2.0,5.0};
auto c2 = make_tagged_compare([](){});
auto mm2 = dummy_minmax(std::begin(x2),std::end(x2),c2);
std::cout << mm2.first << " " << mm2.second << " " << c2.count;
}
完整的示例