Элегантный код для поиска 5-ти максимального числа из 3-х массивов
Я прочитал это блог где программист C # показывает, как использовать LINQ для извлечения 5 верхних чисел из 3 различных массивов.
Я попытался сделать то же самое с C ++ и написал следующее, всего 5 строк кода, используя vector, и sort. Выход 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;
}
Решение
Я бы использовал 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),
Если вы хотите иметь самые большие элементы в порядке, вы можете использовать std::partial_sort вместо std::nth_element или сделать постобработку std::sort на первые 5 элементов v, Сложность std::partial_sort для верхних элементов K O(N log K), который подходит O(N log N) для полной сортировки. За K=5должна быть небольшая разница между std::nth_element а также std::partial_sort,
Другие решения
Большинство решений, предусматривающих сортировку массива (либо всего массива, либо отдельных под-массивов), будут неоптимальными с точки зрения сложности времени. Вся сортировка на основе сравнения требует минимума сложности 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"));
}
По крайней мере, ИМО, которая квалифицируется как довольно элегантная — четкая, лаконичная и эффективная.
Еще один хороший способ сделать это 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
}
Я интерпретирую «лучше» как лучшую сложность времени = более быстрый алгоритм. Если вы стремитесь к другому «лучше», тогда, пожалуйста, пренебрегайте моим постом.
Несмотря на то, что вы не указали, что три массива отсортированы, они являются фактическими в вашей программе. Итак, предполагая, что три массива всегда отсортированы, вы можете сделать улучшение:
(Следующий код является более псевдокодом, чем C ++, извините, но у меня нет атм компилятора C ++)
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;
}
}
и решение находится в массиве «решение». Если массивы НЕ отсортированы, небольшое улучшение будет состоять в том, чтобы сначала отсортировать три массива по отдельности, а затем использовать приведенный выше алгоритм.
Вы можете использовать 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 массив, который является ответом.
Вы можете иметь небольшую функцию, которая возвращает максимум три и вызывать ее умным способом:
#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 лучших лошадей, учитывая, что вы можете участвовать только в трех из них одновременно.
detector