1

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

我尝试用 C++ 做同样的事情并编写了以下代码，使用向量和排序只有 5 行代码。输出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;
}
4

6 回答 6

3

我会boost::zip_iterator优雅地附加 3 个输入数组，并std::nth_element以std::greater未指定的顺序获取 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)。

如果您想按顺序排列最大的元素，您可以使用 astd::partial_sort代替，也可以对 的前 5 个元素进行std::nth_element后处理。前 K 个元素的复杂度为，接近于完整排序。因为和之间应该没有什么区别。std::sortvstd::partial_sortO(N log K)O(N log N)K=5std::nth_elementstd::partial_sort

于 2013-09-17T07:21:37.720 回答
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 上，它相当优雅——清晰、简洁和高效。

于 2013-09-17T07:29:37.453 回答
1

另一个不错的方法是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
}
于 2013-09-17T16:56:21.073 回答
0

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

#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("%d\n", val);
    count ++;

    if (val == a1[last1]) {
        last1 --;
    } else if (val1 == a2[last2]) {
        last2 --
    } else {
        last3 --;
    }
} while (count <= 5);

鉴于您一次只能比赛其中三匹马，这与通过最少比赛次数找到前 5 匹马的老难题非常相似。

于 2013-09-17T08:03:48.517 回答
0

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

尽管您没有说明这三个数组已排序，但它们实际上在您的程序中。所以，假设三个数组总是排序的，你可以做一个改进：（下面的代码比 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;
    }
}

并且解决方案在“解决方案”数组中。如果数组没有排序，稍微改进一下是先分别对三个数组进行排序，然后使用上述算法。

于 2013-09-17T06:58:30.070 回答
0

您可以使用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。

于 2013-09-17T07:07:57.320 回答