如何有效地找到数组中三元组的最大平均值?

问题描述 投票:1回答:2

我有一个数字数组int arr[] = {4, 7, 8, 9, 2, 4, 7, 3, 5};并且我需要找到3个三元组(它们不需要是连续的),它们的平均值最大。

有什么想法吗?

c++ algorithm big-o combinations combinatorics
2个回答
0
投票

如果三元组可以重叠(包含一些共同点),则:

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),但很可能在线性时间内运行。


0
投票

您可以使用排序和选择,例如在

#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;
}

如果不希望有重叠值,则只需选择其他索引。

© www.soinside.com 2019 - 2024. All rights reserved.