优雅的代码，从 5 数组中找到 3 个最大数字

Question

我读过那篇博客，其中一位 C# 程序员展示了如何使用 LINQ 从 3 个不同的数组中提取前 5 个数字。

我尝试对C++做同样的事情，并编写了以下内容，只有 5 行代码使用 vector，然后排序。输出按预期88 89 110 888 921。

但问题是，你有更好的解决方案吗？

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
    int Array1 [] = { 9, 65, 87, 89, 888 };
    int Array2 [] = { 1, 13, 33, 49, 921 };
    int Array3 [] = { 22, 44, 66, 88, 110 };
    vector<int> A1(begin(Array1), end(Array1)); 
    A1.insert(end(A1), begin(Array2), end(Array2)); 
    A1.insert(end(A1), begin(Array3), end(Array3));
    sort(begin(A1), end(A1));
    vector<int> max(end(A1)-5, end(A1));
    copy(begin(max), end(max), ostream_iterator<int>(cout, " "));
    return 0;
}

Answer 1

我会使用 boost::zip_iterator 来附加 3 个输入数组，并使用 std::greater std::nth_element以未指定的顺序获取 5 个最大的元素

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
#include <boost/iterator/zip_iterator.hpp>
int main()
{
    int Array1 [] = { 9, 65, 87, 89, 888 };
    int Array2 [] = { 1, 13, 33, 49, 921 };
    int Array3 [] = { 22, 44, 66, 88, 110 };
    std::vector<int> v;
    v.reserve((sizeof(Array1) + sizeof(Array2) + sizeof(Array3)) / sizeof(int));
    std::for_each(
        boost::make_zip_iterator(boost::make_tuple(std::begin(Array1), std::begin(Array2), std::begin(Array3))),
        boost::make_zip_iterator(boost::make_tuple(std::end(Array1), std::end(Array2), std::end(Array3))),
        [&v](boost::tuple<int, int, int> const& t) {
            v.push_back(t.get<0>()); v.push_back(t.get<1>()); v.push_back(t.get<2>());
        }
    );
    std::nth_element(begin(v), begin(v) + 5, end(v), std::greater<int>());
    std::copy(begin(v), begin(v) + 5, std::ostream_iterator<int>(std::cout, " "));
}

活生生的例子。

复杂度：线性O(N1 + N2 + N3)。

如果要按顺序排列最大的元素，可以使用std::partial_sort而不是std::nth_element，或者对v的前 5 个元素进行后处理std::sort。前 K 个元素的std::partial_sort复杂度O(N log K)，接近O(N log N)完全排序。对于K=5，std::nth_element和std::partial_sort之间应该没有什么区别。

Answer 2

大多数涉及对数组（完整数组或单独子数组）进行排序的解决方案在时间复杂度方面都是次优的。所有基于比较的排序都需要最小的 O（N log N） 复杂性。像桶排序或基数排序之类的东西可以减少这种情况，但只有相当具体的限制（这可能不适用于这里）。

在我看来，对于这项任务，线性复杂性应该是可能的，所以这就是我们真正想要的。

此外，我将假设 5 行代码的目标仅包含可执行语句（即，像 #include 这样的东西不算在内），允许使用 C++11，并且即使问题中的数据碰巧被排序，即使数据没有排序，它也应该工作。

考虑到这些条件/假设，我会像这样做这项工作：

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
int main() {
    std::vector<int> A1{ 9, 65, 87, 89, 888 };
    A1.insert(A1.end(), { 1, 13, 33, 49, 921 });
    A1.insert(A1.end(), { 22, 44, 66, 88, 110 });
    std::nth_element(A1.begin(), A1.end() - 5, A1.end());
    std::copy(A1.end() - 5, A1.end(), std::ostream_iterator<int>(std::cout, "n"));
}

至少IMO，这是相当优雅的 - 清晰，简洁和高效。

Answer 3

另一个不错的方法是boost.accumulators：

#include <iostream>
#include <vector>
#include <string>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics.hpp>
int main(int argc, char* argv[])
{
    int Array1 [] = { 9, 65, 87, 89, 888 };
    int Array2 [] = { 1, 13, 33, 49, 921 };
    int Array3 [] = { 22, 44, 66, 88, 110 };
    using namespace boost::accumulators;
    // this will accumulate the 5 largest numbers 
    accumulator_set<int, features< tag::tail<right> > > acc (
        tag::tail<right>::cache_size = 5);
    // combine the arrays into a single iterator range
    // and then apply for_each once, if you like
    acc = std::for_each(Array1, Array1 + 5, acc);
    acc = std::for_each(Array2, Array2 + 5, acc);
    acc = std::for_each(Array3, Array3 + 5, acc);
    for(int n : tail(acc))
        std::cout << n << ' '; // 921, 888, 110, 89, 88
}

Answer 4

我将"更好"解释为更好的时间复杂度=更快的算法。如果您的目标是不同的"更好"，那么请忽略我的帖子。

虽然您没有说明这三个数组已排序，但实际上在您的程序中。因此，假设这三个数组始终排序，您可以进行改进：（以下代码比C++更伪代码，抱歉我没有C++编译器atm）

int i1 = Array1.size();
int i2 = Array2.size();
int i3 = Array3.size();
int n = 5;
int solution[n];
while (n > 0) {
    n = n - 1;
    if (Array1[i1] >= Array2[i2] && Array1[i1] >= Array3[i3]) {
        solution[n] = Array1[i1];
        i1 = i1 - 1;
    } else if (Array2[i2] >= Array1[i1] && Array2[i2] >= Array3[i3]) {
        solution[n] = Array2[i2];
        i2 = i2 - 1;
    } else {
        solution[n] = Array3[i3];
        i3 = i3 - 1;
    }
}

解决方案在"解决方案"数组中。如果数组没有排序，稍微改进的是先单独对三个数组进行排序，然后使用上述算法。

Answer 5

您可以使用

O(n)算法来解决此问题（您的代码使用排序，这是O (n log n)。我还没有测试过它，但是如果您的输入数组未排序，它应该可以工作。

vector<int> getTop3(vector<int> A) {
    vector<int> top3;
    int max1 = A[0];
    int max2 = A[0];
    int max3 = A[0];
    for (unsigned i = 0; i < A.size(); i++) {
        if (max1 > A[i]) {
            max3 = max2;
            max2 = max1;
            max1 = A[i];
        }
        else if (max2 > A[i]) {
            max3 = max2;
            max2 = A[i];
        }
        else if (max3 > A[i]) {
            max3 = A[i];
        }
    }
    top3.push_back(max1);
    top3.push_back(max2);
    top3.push_back(max3);
    return top3;
}

然后在您的主函数中：

temp.insert(temp.end(), getTop3(v1).begin(), getTop3(v1).end());
temp.insert(temp.end(), getTop3(v2).begin(), getTop3(v2).end());
temp.insert(temp.end(), getTop3(v3).begin(), getTop3(v3).end());
vector<int> ans = getTop3(temp);

基本上，它从三个输入向量/数组中的每一个中找到前三个元素，并将这九个元素插入temp数组中。然后它从 temp 数组中找到前三个元素，即 ans。

Answer 6

你可以有一个小函数，它返回最大值 3 并以智能方式调用它：

#define max(a, b) ((a) > (b)) ? (a) : (b)
int maxofthree(int a, int b, int c)
{
    return max(max(a, b), c);
}
count = 0;
do {
    int val = maxofthree(a1[last1], a2[last2], a3[last3]);
    printf("%dn", val);
    count ++;
    if (val == a1[last1]) {
        last1 --;
    } else if (val1 == a2[last2]) {
        last2 --
    } else {
        last3 --;
    }
} while (count <= 5);

这与找到前 5 匹马的比赛次数最少的旧谜题非常相似，因为您一次只能比赛其中的三匹。