Najszybszy sposób na znalezienie minimalnego iloczynu 2 elementów tablicy zawierających ponad 200 000 elementów

13

Mam tablicę a[n]. Numer njest wprowadzany przez nas. Muszę znaleźć minimalny produkt a[i]i a[j]jeśli:

1) abs(i - j) > k

2) a[i] * a[j]jest zminimalizowany

Oto moje rozwiązanie (bardzo naiwne):

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

Ale chcę wiedzieć, czy istnieje szybszy sposób na znalezienie minimalnego produktu z odległością?

Mouvre
źródło
7
Dlaczego nie powinienem #include <bits / stdc ++. H>? i C ++ zapewniają tylko tablicę zmiennej długości według rozszerzenia kompilatora. Dlaczego nie używasz std::vector? @Scheff - sortowanie zniszczyłoby pierwotne relacje „odległości”.
David C. Rankin
3
Przynajmniej kontrolę if (i!=j) if (abs(i - j) > k)można wyeliminować. Wystarczy uruchomić wewnętrzną pętlę w I + k + 1: for (ll j = i + k + 1; j < n; ++j). Sprawdzanie za pomocą firstmożna również wyeliminować, jeśli mnzostanie zainicjowane przed np mn = a[0] * a[k + 1];. Za pomocą . (Być może knależy to sprawdzić na npoczątku, aby uczynić to kuloodpornym.) Ale wciąż jest to O (N²). To musi być wykonalne szybciej ...
Scheff,
2
@PaulMcKenzie Pokaż jedno zapytanie z nie mniej niż dwoma przydatnymi trafieniami wśród pierwszych dziesięciu dla minimalnego produktu z odległością indeksu (lub maksymalną).
Greybeard
1
@PaulMcKenzie „Prawdopodobnie istnieją setki, jeśli nie tysiące linków URL, które pokazują odpowiedzi na to pytanie”. - udostępnij przynajmniej trzy z tych adresów URL.
ב ברקן
2
Skąd pochodzi to pytanie? To nie brzmi jak coś, co po prostu zrobiono z cienkiego powietrza. Nie zdziwiłbym się, gdyby pochodziła z jednej z tych witryn internetowych. Jeśli tak, na tych stronach prawdopodobnie trwają długie dyskusje na temat rozwiązania problemu, jeśli nie pełne rozwiązania.
PaulMcKenzie

Odpowiedzi:

12

Zakładając, że jest co najmniej jedna para elementów spełniających warunki i nie ma w niej mnożenia się dwóch elementów, można to zrobić w najgorszym i najlepszym przypadku w Theta(n-k)czasie i Theta(1)przestrzeni, z czymś takim:

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;

Jest to optymalne pod względem asymptotycznej złożoności najgorszego przypadku zarówno w czasie, jak i przestrzeni, ponieważ optymalny produkt może znajdować a[0]się n-(k+1)co najmniej z dowolnym elementem w odległości k+1, więc co najmniej n-(k+1)liczby całkowite muszą być odczytane przez dowolny algorytm rozwiązujący problem.


Idea stojąca za algorytmem jest następująca:

Optymalny produkt wykorzystuje dwa elementy a, zakładając, że są to a[r]i a[s]. Bez utraty ogólności możemy założyć, że s > rponieważ produkt jest przemienny.

Z powodu ograniczenia abs(s-r) > kto implikuje s >= k+1. Teraz skażdy z indeksów może spełniać ten warunek, więc powtarzamy te wskaźniki. Taka jest iteracja ipokazanego kodu, ale jest ona przesuwana k+1dla wygody (tak naprawdę nie ma znaczenia). Dla każdej iteracji musimy znaleźć optymalny produkt o i+k+1największym indeksie i porównać go z poprzednią najlepszą oceną.

Możliwe indeksy, i+k+1z którymi można się sparować, są wszystkie mniejsze lub równe ize względu na wymaganą odległość. Musielibyśmy również powtórzyć te wszystkie, ale nie jest to konieczne, ponieważ minimum a[i+k+1]*a[j]przekroczenia justalonego ijest równe min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))monotoniczności produktu (biorąc minimum w odniesieniu zarówno do minimum, jak i maksimum, z a[j]uwzględnieniem dwóch możliwych oznaki a[i+k+1]lub równoważnie dwa możliwe kierunki monotoniczności).

Ponieważ zbiór a[j]wartości, nad którymi możemy zoptymalizować jest tu po prostu {a[0], ..., a[i]}, co po prostu narośl przez jeden element ( a[i]) w każdej iteracji i, możemy po prostu śledzić max(a[j])i min(a[j])z pojedynczych zmiennych, aktualizując je, jeśli a[i]jest większy lub mniejszy niż w poprzednich wartości optymalnych. Odbywa się to back_maxi back_minna przykładzie kodu.

Pierwszy krok iteracji ( i=0) jest pomijany w pętli i zamiast tego wykonywany jako inicjalizacja zmiennych.

orzech włoski
źródło
3
@ Greybeard Nie muszę ich trzymać, ponieważ jedynymi możliwymi kandydatami na optymalny produkt a[i+k+1]są minimum i maksimum.
orzech
czy możesz wyjaśnić, dlaczego algorytm działa w twojej odpowiedzi?
MinaHany
6

Nie jestem pewien co do najszybszego .

Dla prostszego problemu bez i <j - k , minimalny produkt należy do produktów par dwóch najmniejszych i największych elementów.

Tak więc (poniższe czynności są zbyt skomplikowane, patrz odpowiedź orzecha włoskiego )
(• pomiń, jeśli k ≤ n
  • zainicjuj minProdukt na [0] * a [k + 1])

  • utrzymuj dwie dynamiczne struktury danych minmax do góry i dalejIplusK,
    zaczynając od {} i {a [ j ] | kj }
  • dla każdego i od 0 do n - k - 1
    • dodaj [ i ] do upToI
    • usuń [ i + k ] z beyondIplusK
    • sprawdź, czy jest nowy minimalny produkt spośród
      min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
      max ( upToI ) × min ( beyondIplusK ) i max ( upToI ) × max ( beyondIplusK )
siwobrody
źródło
Powinno to być najszybsze, przynajmniej pod względem złożoności. Jest to czas O i czas przechowywania.
smttsp
oryginalne rozwiązanie ma złożoność O (N ** 2), jak oceniasz złożoność swojego rozwiązania?
lenik
O (nlogn) time, O (n) space (dla odpowiednich implementacji minmax)
greybeard
@starzec. Dlaczego potrzebujesz n * czasu logowania. Dlaczego nie po prostu utrzymanie 4 * n tablicę, która zawiera minUpto, maxUpto, minBeyond, maxBeyond(można tworzyć w dwóch iteracjach)? Następnie, w trzeciej iteracji, dla każdego indeksu znajdź minimalne możliwe mnożenie.
smttsp
(@smttsp Byłoby to alternatywny etap w kierunku Walnut w roztworze ).
starzec
4

Dla „minimalnej wielkości”

Znajdź 2 elementy „najmniejszej wielkości”, a następnie (po znalezieniu dwóch zer lub przeszukaniu całej tablicy) pomnóż je.

Dla „najniższej wartości” bez abs(i - j) > kczęści

Istnieją 3 możliwości:

  • dwie najwyższe (najmniejszej wielkości) liczby ujemne

  • dwie najniższe (najmniejsze wielkości) liczby nieujemne

  • najniższa (największa jasność) liczba ujemna i najwyższa (największa jasność) liczba nieujemna

Możesz wyszukać wszystkie 6 wartości i dowiedzieć się, które produkty są najlepsze na koniec.

Jednak; jak tylko zobaczysz zero, wiesz, że nie musisz więcej wiedzieć o pierwszych 2 możliwościach; a gdy tylko zobaczysz jedną liczbę ujemną i jedną nieujemną, wiesz, że zależy ci tylko na trzeciej możliwości.

Prowadzi to do skończonej maszyny stanów z 3 stanami - „dbaj o wszystkie 3 możliwości”, „odpowiedź wynosi zero, chyba że liczba ujemna jest widoczna” i „dbaj tylko o ostatnią możliwość”. Można to zaimplementować jako zestaw 3 pętli, gdzie 2 pętle wskakują do ( goto) środka innej pętli, gdy zmienia się stan (maszyny skończonej).

W szczególności może to wyglądać nieco niejasno (nieprzetestowane):

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

Dla „najniższej wartości” z abs(i - j) > kczęścią

W tym przypadku nadal masz 3 możliwości; i może sprawić, że będzie działać z tym samym podejściem „3 pętle ze skończoną maszyną stanów”, ale robi się zbyt bałaganiarski / brzydki. W tym przypadku lepszym rozwiązaniem jest wstępne skanowanie tablicy w celu ustalenia, czy są jakieś zera i czy wszystkie są ujemne czy wszystkie dodatnie; aby po wstępnym skanowaniu można było wiedzieć, że odpowiedź wynosi zero, lub wybrać pętlę zaprojektowaną tylko dla konkretnej możliwości.

Brendan
źródło
1
Gdzie to bierze się za dolną granicę k różnicy indeksu?
Greybeard
1
@greybeard: Nie ma (tęskniłem za tą częścią) - kod musiałby zostać zmodyfikowany, aby wziąć to pod uwagę.
Brendan,
Dlaczego potrzebujesz dwóch zer?
TrentP
@TrentP: Argh - masz rację. Wystarczy jedno zero, aby wiedzieć, że odpowiedź to 0 lub liczba ujemna.
Brendan