Elegant code to find the 5 max top number from 3 Array

Question

I read that blog where a C# programmer show how to use LINQ to extract the 5 top numbers from 3 different Array.

I tried to do the same with C++ and wrote the following, only 5 line of code using vector, and sort. The output is 88 89 110 888 921 as expected.

But have the question is, have you a better solution ?

#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

I'd use boost::zip_iterator to eleganty append the 3 input arrays, and std::nth_element with std::greater to get the 5 largest elements in unspecified order

#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, " "));
}

Live Example.

Complexity: linear O(N1 + N2 + N3).

If you want to have the largest elements in order, you could either use a std::partial_sort instead of std::nth_element or do a post-processing std::sort on the first 5 elements of v. The complexity of std::partial_sort for the top K elements is O(N log K), which approaches O(N log N) for a full sort. For K=5, there should be little difference between std::nth_element and std::partial_sort.

Answer 2

Most solutions that involve sorting the array (either the complete array, or the sub-arrays individually) will be sub-optimal in terms of time complexity. All comparison-based sorting requires a minimum of O(N log N) complexity. Something like a bucket sort or radix sort can reduce that, but only with fairly specific limitations (that may not apply here).

It seems to me that for this task, linear complexity should be possible, so that's what we really want.

Further, I'm going to assume that the target of 5 lines of code includes only executable statements (i.e., things like #include don't count), that C++11 is allowed, and that even though the data in the question happens to be sorted, it should work even if the data isn't sorted.

With those conditions/assumptions in mind, I'd do the job like this:

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

At least IMO, that qualifies as fairly elegant -- clear, concise and efficient.

Answer 3

Yet another nice way to do this is 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

I interpret "better" as in better time complexity = faster algorithm. If you aim for a different "better" then please neglect my post.

Although you have not stated that the three arrays are sorted, the are infact in your program. So, assuming the three arrays are always sorted, you could do an improvment: (The following code is more pseudo-code than C++, sorry but I do not have a C++ compiler 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;
    }
}

and the solution is in the "solution" array. If the arrays are NOT sorted, a slight improvment would be to sort the three arrays individually first and then use the above algorithm.

Answer 5

You can use an O(n) algorithm to solve this problem (Your code uses sorting, which is O (n log n). I haven't tested it yet, but it should work if your input arrays are unsorted.

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

Then in your main function:

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

Basically, it finds top three elements from each of the three input vectors/arrays and insert these nine elements in the temp array. Then it finds the top three elements from the temp array, which is the ans.

Answer 6

You can have a small function that returns the max of three and call it in a smart way:

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

This is quite similar to the old puzzle of the least number of races to find the top 5 horses given that you can race only three of them at a time.