我有一个数字数组int arr[] = {4, 7, 8, 9, 2, 4, 7, 3, 5};
并且我需要找到3个三元组(它们不需要是连续的),它们的平均值最大。
有什么想法吗?
如果三元组可以重叠(包含一些共同点),则:
1. use quickselect to find the 4 largest elements in linear time.
2. Say these are a, b, c, d, with a being the largest.
3. {a,b,c}, {a,b,d}, {a,c,d}
如果三元组不能重叠,则如上所述,但是在线性时间内找到9个最大元素,并返回{a,b,c},{d,e,f},{g,h,i}(其中9个元素未排序)。
为什么这样做?三胞胎中的一个元素与三胞胎中的一个元素(而不是另一个三胞胎)之间的任何交换都将以较大的元素交换为较小的元素(如果重复,则相等)。
请注意,快速选择在一般情况下是线性的,在最坏情况下为O(n ^ 2),但很可能在线性时间内运行。
您可以使用排序和选择,例如在
#include <iostream>
#include <algorithm>
int main() {
// The test data
int arr[] = { 4, 7, 8, 9, 2, 4, 7, 3, 5 };
// Getting the size
unsigned int sizeOfArray = sizeof(arr) / sizeof(int);
// Only, if we have at least 4 elements, we can build triplets
if (sizeOfArray > 3) {
std::sort(arr, arr + sizeOfArray);
// Triplet 1
double average = (double)(arr[sizeOfArray - 1] + arr[sizeOfArray - 2] + arr[sizeOfArray - 3]) / 3.0;
std::cout << "Triplet 1: " << arr[sizeOfArray - 3] << ' ' << arr[sizeOfArray - 2] << ' ' << arr[sizeOfArray - 1]
<< "\t Average: " << average << '\n';
// Triplet 2
average = (double)(arr[sizeOfArray - 1] + arr[sizeOfArray - 2] + arr[sizeOfArray - 4]) / 3.0;
std::cout << "Triplet 3: " << arr[sizeOfArray - 1] << ' ' << arr[sizeOfArray - 2] << ' ' << arr[sizeOfArray - 4]
<< "\t Average: " << average << '\n';
// Triplet 3
average = (double)(arr[sizeOfArray - 1] + arr[sizeOfArray - 2] + arr[sizeOfArray - 4]) / 3.0;
std::cout << "Triplet 1: " << arr[sizeOfArray - 1] << ' ' << arr[sizeOfArray - 3] << ' ' << arr[sizeOfArray - 4]
<< "\t Average: " << average << '\n';
}
else {
std::cerr << "\n*** Error: Not enough data\n";
}
return 0;
}
如果需要唯一值,则将数据放入std::set
:
#include <iostream>
#include <algorithm>
#include <set>
#include <iterator>
int main() {
// The test data
int arr[] = { 4, 7, 8, 9, 2, 4, 7, 3, 5 };
// Getting the size
unsigned int sizeOfArray = sizeof(arr) / sizeof(int);
std::set<int> intSet(arr, arr + sizeOfArray);
// Only, if we have at least 4 elements, we can build triplets
if (intSet.size() > 3) {
std::set<int>::reverse_iterator iter = intSet.rbegin();
int v1 = *iter++;
int v2 = *iter++;
int v3 = *iter++;
int v4 = *iter;
// Triplet 1
double average = static_cast<double>(v1 + v2 + v3) / 3.0;
std::cout << "Triplet 1: " << v1 << ' ' << v2 << ' ' << v3 << "\t Average: " << average << '\n';
// Triplet 2
average = static_cast<double>(v1 + v2 + v4) / 3.0;
std::cout << "Triplet 2: " << v1 << ' ' << v2 << ' ' << v4 << "\t Average: " << average << '\n';
// Triplet 3
average = static_cast<double>(v1 + v3 + v4) / 3.0;
std::cout << "Triplet 3: " << v1 << ' ' << v3 << ' ' << v4 << "\t Average: " << average << '\n';
}
else {
std::cerr << "\n*** Error: Not enough data\n";
}
return 0;
}
如果不希望有重叠值,则只需选择其他索引。