Самый быстрый способ найти минимальное произведение из 2 элементов массива, содержащих более 200 000 элементов

13

У меня есть массив a[n]. Номер nвводится нами. Мне нужно найти минимальный продукт a[i]и a[j]если:

1) abs(i - j) > k

2) a[i] * a[j]минимизируется

Вот мое решение (очень наивное):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

Но я хочу знать, есть ли более быстрый способ найти минимальный продукт с расстоянием?

Mouvre
источник
7
Почему я не должен включать #include <bits / stdc ++. H>? и C ++ предоставляет массив переменной длины только расширением компилятора. Почему вы не используете std::vector? @Scheff - сортировка разрушила бы исходные «дистанционные» отношения.
Дэвид С. Ранкин
3
По крайней мере, проверка if (i!=j) if (abs(i - j) > k)может быть устранена. Просто начните внутреннюю петлю I + к + 1: for (ll j = i + k + 1; j < n; ++j). Проверка с помощью firstможет быть также отменена, если mnинициализирована до, например, с mn = a[0] * a[k + 1];. (Может kбыть, nсначала нужно проверить, чтобы сделать это пуленепробиваемым.) Но это все равно O (N²). Это должно быть выполнимо быстрее ...
Scheff
2
@PaulMcKenzie Пожалуйста, покажите один запрос с не менее чем двумя полезными хитами среди первой десятки для минимального продукта с индексным расстоянием (или максимальным).
седобородый
1
@PaulMcKenzie «Возможно, есть сотни, если не тысячи URL-ссылок, которые показывают ответы на этот вопрос». - Пожалуйста, поделитесь хотя бы тремя из этих URL.
גלעד ברקן
2
Откуда этот вопрос? Это не похоже на что-то, сделанное из воздуха. Я не удивлюсь, если это с одного из этих сайтов "онлайн-судьи". Если это так, то на этих сайтах, вероятно, затянулись дискуссии о решении проблемы, если не о полном решении.
PaulMcKenzie

Ответы:

12

Предполагая, что есть хотя бы одна пара элементов, удовлетворяющих условиям, и нет умножения двух элементов в ней, переполнения, это может быть сделано во Theta(n-k)времени и Theta(1)пространстве в наихудшем и наилучшем случае, с чем-то вроде этого:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

Это оптимально с точки зрения асимптотической сложности в худшем случае как для времени, так и для пространства, поскольку оптимальным произведением может быть как минимум a[0]любой из n-(k+1)элементов на расстоянии k+1, поэтому n-(k+1)любой алгоритм, решающий проблему, должен быть прочитан как минимум целыми числами.


Идея алгоритма заключается в следующем:

Оптимальный продукт использует два элемента a, предположим, что это a[r]и a[s]. Без ограничения общности можно предположить, что, s > rпоскольку произведение является коммутативным.

Из-за ограничения abs(s-r) > kэто означает, что s >= k+1. Теперь sкаждый из индексов может удовлетворять этому условию, поэтому мы перебираем эти индексы. Это итерация iв показанном коде, но k+1для удобства она сдвинута (не имеет большого значения). Для каждой итерации нам нужно найти оптимальный продукт с i+k+1наибольшим индексом и сравнить его с предыдущим лучшим предположением.

Все возможные индексы, i+k+1с которыми нужно соединиться, являются меньшими или равными iиз-за требования к расстоянию. Нам также нужно было бы повторить все это, но в этом нет необходимости, потому что минимальный a[i+k+1]*a[j]избыточный jпри фиксированном iравен min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))монотонности продукта (принимая во внимание минимум как по отношению к минимуму, так и максимальный по сравнению a[j]с учетом двух возможных признаки a[i+k+1]или эквивалентно два возможных направления монотонности.)

Так как набор a[j]значений, для которых мы оптимизируем здесь, просто {a[0], ..., a[i]}, который просто увеличивается на один элемент ( a[i]) в каждой итерации i, мы можем просто отслеживать max(a[j])и min(a[j])с отдельными переменными, обновляя их, если они a[i]больше или меньше предыдущих оптимальных значений. Это делается с помощью back_maxи back_minв примере кода.

Первый шаг итерации ( i=0) пропускается в цикле и вместо этого выполняется как инициализация переменных.

грецкий орех
источник
3
@greybeard Мне не нужно держать их рядом, потому что единственными возможными кандидатами на оптимальный продукт a[i+k+1]являются минимум и максимум.
грецкий орех
Не могли бы вы объяснить, почему алгоритм работает в вашем ответе?
MinaHany
6

Не уверен насчет самого быстрого .

Для более простой задачи без i <j - k минимальное произведение находится среди произведений пар из двух наименьших и самых больших элементов.

Итак, (следующее слишком сложно, см . Ответ грецкого ореха )
(• прекратить, если k ≤ n
  • инициализировать minProduct a [0] * a [k + 1])

  • сохранить две динамические структуры данных minmax upToI и beyondIplusK,
    начиная с {} и {a [ j ] | kj }
  • для каждого i от 0 до n - k - 1
    • добавить [ i ] в upToI
    • удалить [ i + k ] из beyondIplusK
    • проверить наличие нового минимального продукта среди
      min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
      max ( upToI ) × min ( beyondIplusK ) и max ( upToI ) × max ( beyondIplusK )
седоборода
источник
Это должно быть самым быстрым, хотя бы по сложности. Это O (n) время и память.
smttsp
исходное решение имеет сложность O (N ** 2), как вы оцениваете сложность вашего решения?
ленник
O (nlogn) время, O (n) пространство (для подходящих реализаций minmax)
седобород
@greybeard. * Зачем вам нужно * время входа в систему. Почему бы не просто сохраняя * п массив 4 , который содержит minUpto, maxUpto, minBeyond, maxBeyond(Вы можете создать в двух итераций)? Затем на третьей итерации для каждого индекса найдите минимально возможное умножение.
smttsp
(@smttsp Это было бы альтернативой шагом в направлении грецкого ореха в растворе .)
старик
4

Для «минимальной величины»

Найдите 2 элемента «наименьшей величины», затем (после того, как вы нашли два нуля или произвели поиск по всему массиву), умножьте их.

Для «наименьшего значения» без abs(i - j) > kдетали

Есть 3 варианта:

  • два старших (наименьшей величины) отрицательных числа

  • два наименьших (наименьшей величины) неотрицательных числа

  • наименьшее (наибольшая величина) отрицательное число и наибольшее (наибольшая величина) неотрицательное число

Вы можете найти все 6 значений и выяснить, какие продукты являются лучшими в конце.

Однако; как только вы видите ноль, вы знаете, что вам больше не нужно знать о первых двух возможностях; и как только вы видите одно отрицательное число и одно неотрицательное число, вы понимаете, что вам важна только третья возможность.

Это приводит к конечному автомату с 3 состояниями - «заботиться обо всех 3 возможностях», «ответ равен нулю, если не видно отрицательное число» и «заботится только о последней возможности». Это может быть реализовано как набор из 3 циклов, где 2 цикла переходят ( goto) в середину другого цикла, когда состояние (конечного автомата) изменяется.

В частности, это может выглядеть примерно так (не проверено):

   // It could be any possibility

   for(ll i=0;i<n;i++) {
       if(a[i] >= 0) {
            if(a[i] < lowestNonNegative1) {
                lowestNonNegative2 = lowestNonNegative1;
                lowestNonNegative1 = a[i];
            }
            if(lowestNonNegative2 == 0) {
                goto state2;
            }
       } else {
            if(a[i] > highestNegative1) {
                highestNegative2 = highestNegative1;
                highestNegative1= a[i];
            }
            if(lowestNonNegative1 < LONG_MAX) {
                goto state3;
            }
       }
   }
   if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
       cout << lowestNonNegative2 * lowestNonNegative1;
   } else {
       cout << highestNegative2 * highestNegative1;
   }
   return;

   // It will be zero, or a negative and a non-negative

   for(ll i=0;i<n;i++) {
state2:
       if(a[i] < 0) {
           goto state3;
       }
   }
   cout << "0";
   return;

   // It will be a negative and a non-negative

   for(ll i=0;i<n;i++) {
state3:
       if(a[i] < lowestNegative) {
           lowestNegative = a[i];
       } else if(a[i] > highestNonNegative) {
           highestNonNegative = a[i];
       }
    }
    cout << lowestNegative * highestNonNegative;
    return;

Для "наименьшего значения" с abs(i - j) > kчастью

В этом случае у вас все еще есть 3 возможности; и может заставить его работать с тем же подходом «3 цикла с конечным автоматом», но он становится слишком грязным / безобразным. В этом случае лучшей альтернативой может быть предварительное сканирование массива, чтобы определить, есть ли нули и все ли они отрицательные или все положительные; так что после предварительного сканирования вы можете узнать, что ответ равен нулю, или выбрать цикл, предназначенный только для конкретной возможности.

Brendan
источник
1
Где это объясняет нижнюю границу k разницы индексов?
седобородый
1
@greybeard: Это не так (я пропустил эту часть) - код должен быть изменен, чтобы учесть это.
Брендан
Зачем вам нужны два нуля?
TrentP
@TrentP: Argh - вы правы. Достаточно одного ноля, чтобы знать, что ответ либо 0, либо отрицательное число.
Брендан