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_iterator3つの入力配列をエレガントに追加し、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)。

最大の要素を順番に並べたい場合は、 のstd::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 に答える
0

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

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

これは、一度に 3 頭しか出走できないことを考えると、上位 5 頭の馬を見つけるための最少出走数の古いパズルに非常によく似ています。

于 2013-09-17T08:03:48.517 に答える
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);

基本的に、3 つの入力ベクトル/配列のそれぞれから上位 3 つの要素を見つけ、これらの 9 つの要素を配列に挿入しますtemp。次に、配列から上位 3 つの要素を見つけtempます。これが ans です。

于 2013-09-17T07:07:57.320 に答える
0

私は「より良い」をより良い時間の複雑さ = より速いアルゴリズムとして解釈します。別の「より良い」を目指す場合は、私の投稿を無視してください。

3 つの配列がソートされているとは述べていませんが、実際にはプログラム内にあります。したがって、3 つの配列が常にソートされていると仮定すると、改善を行うことができます。

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

ソリューションは「ソリューション」配列にあります。配列がソートされていない場合、最初に 3 つの配列を個別にソートしてから上記のアルゴリズムを使用すると、わずかな改善が得られます。

于 2013-09-17T06:58:30.070 に答える