Ключ к вашему ответу лежит в ваших наблюдениях ...
Если мы сначала отсортируем два массива A и B, а затем умножим их вместе, мы получим
2 8 14 18 7 28 49 63 8 32 56 72 11 44 77 99 который является массивом с m
отсортированные подмассивы.
Таким образом, существует n последовательностей данных, которые сортируются, и проблема заключается в том, чтобы использовать их для генерации ответа.
Подсказка 1: Вы можете решить эту проблему, используя очередь приоритетов. Количество элементов в очереди будет таким же, как количество отсортированных списков, которые создаются.
С
#include <vector>
#include <algorithm>
#include <random>
#include <queue>
С учетом следующих структур (C ++)
// helper to catch every tenth element.
struct Counter {
int mCount;
double mSum;
Counter() : mCount(0), mSum(0) {}
void push_back(int val)
{
if (mCount++ % 10 == 0)
{
mSum += val;
}
}
double sum() { return mSum; }
};
// Storage in the priority queue for each of the sorted results.
struct Generator {
int i_lhs;
int i_rhs;
int product;
Generator() : i_lhs(0), i_rhs(0), product(0) {}
Generator(size_t lhs, size_t rhs, int p) : i_lhs(lhs), i_rhs(rhs), product(p)
{
}
};
// comparitor to get lowest value product from a priority_queue
struct MinHeap
{
bool operator()(const Generator & lhs, const Generator & rhs)
{
if (lhs.product > rhs.product) return true;
return false;
}
};
Я измерил ....
double Faster(std::vector<int> lhs, std::vector<int> rhs)
{
Counter result;
if (lhs.size() == 0 || rhs.size() == 0) return 0;
std::sort(lhs.begin(), lhs.end());
std::sort(rhs.begin(), rhs.end());
if (lhs.size() < rhs.size()) {
std::swap(lhs, rhs);
}
size_t l = 0;
size_t r = 0;
size_t lhs_size = lhs.size();
size_t rhs_size = rhs.size();
std::priority_queue<Generator, std::vector< Generator >, MinHeap > queue;
for (size_t i = 0; i < lhs_size; i++) {
queue.push(Generator(i, 0, lhs[i] * rhs[0]));
}
Generator curr;
while (queue.size()) {
curr = queue.top();
queue.pop();
result.push_back(curr.product);
curr.i_rhs++;
if( curr.i_rhs < rhs_size ){
queue.push(Generator(curr.i_lhs, curr.i_rhs, lhs[curr.i_lhs] * rhs[curr.i_rhs]));
}
}
return result.sum();
}
Быстрее, чем следующая наивная реализация
double Naive(std::vector<int> lhs, std::vector<int> rhs)
{
std::vector<int> result;
result.reserve(lhs.size() * rhs.size());
for (size_t i = 0; i < lhs.size(); i++) {
for (size_t j = 0; j < rhs.size(); j++) {
result.push_back(lhs[i] * rhs[j]);
}
}
std::sort(result.begin(), result.end());
Counter aCount;
for (size_t i = 0; i < result.size(); i++) {
aCount.push_back(result[i]);
}
return aCount.sum();
}
Сортировка входных векторов происходит намного быстрее, чем выходной вектор.
Для каждой строки мы создаем генератор, который будет перебирать все столбцы. Текущий продукт добавляется в качестве значения приоритета в очередь, и как только у нас есть все созданные генераторы, мы читаем их из очереди.
Затем, если для каждого генератора остается еще один столбец, мы добавляем его обратно в очередь. Это из наблюдения, что на выходе предварительно отсортированного входа было m подмассивов размера n. Очередь содержит все текущие минимальные значения для каждого подмассива, и наименьшее из этого набора является наименьшим оставшимся из всего списка. Когда генератор удаляется и повторно добавляется, он гарантирует, что значение top является следующим наименьшим элементом результатов.
Цикл по-прежнему равен O (нм), поскольку каждый генератор создается один раз, считывая наименьшее значение O (1), а вставляя в очередь O (log n). Что мы делаем один раз для каждой строки, поэтому O (nm * log n + nm), что упрощается до O (nm log n).
Наивным раствором является O (нм log nm).
Горловина производительности, которую я обнаружил в приведенном выше решении, заключалась в затратах на вставку в очередь, и у меня была повышенная производительность, но я не думаю, что она algorithm значительно выше.