Der schnellste Weg, um ein minimales Produkt von 2 Array-Elementen mit mehr als 200000 Elementen zu finden

13

Ich habe ein Array a[n]. Die Nummer nwird von uns eingegeben. Ich muss das Minimalprodukt von finden a[i]und a[j]wenn:

1) abs(i - j) > k

2) a[i] * a[j]wird minimiert

Hier ist meine Lösung (sehr naiv):

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

Aber ich möchte wissen, ob es einen schnelleren Weg gibt, ein minimales Produkt mit Abstand zu finden?

Mouvre
quelle
7
Warum sollte ich nicht <bits / stdc ++. H> einschließen? und C ++ bieten nur ein Array mit variabler Länge nach Compiler-Erweiterung. Warum benutzt du nicht std::vector? @Scheff - Sortieren würde die ursprünglichen "Distanz" -Beziehungen zerstören.
David C. Rankin
3
Zumindest kann die Prüfung if (i!=j) if (abs(i - j) > k)entfallen. Starten Sie einfach die innere Schleife bei i + k + 1 : for (ll j = i + k + 1; j < n; ++j). Die Prüfung mit firstkann ebenfalls beseitigt werden, wenn sie mnzuvor z mn = a[0] * a[k + 1];. B. mit initialisiert wurde . (Vielleicht ksollte zunächst geprüft werden n, ob dies kugelsicher ist.) Aber es ist immer noch O (N²). Das muss schneller machbar sein ...
Scheff
2
@PaulMcKenzie Bitte zeigen Sie eine Abfrage mit nicht weniger als zwei nützlichen Treffern unter den ersten zehn für ein minimales Produkt mit Indexabstand (oder maximal) an.
Graubart
1
@PaulMcKenzie "Es gibt wahrscheinlich Hunderte, wenn nicht Tausende von URL-Links, die Antworten auf diese Frage anzeigen." - Bitte teilen Sie mindestens drei dieser URLs.
ברקן ברקן
2
Woher kam diese Frage? Es klingt nicht nach etwas, das nur aus dünner Luft besteht. Es würde mich nicht wundern, wenn es von einer dieser "Online-Richter" -Seiten stammt. Wenn ja, werden auf diesen Websites wahrscheinlich lange Diskussionen über die Lösung des Problems geführt, wenn nicht sogar vollständige Lösungen.
PaulMcKenzie

Antworten:

12

Unter der Annahme, dass mindestens ein Elementpaar die Bedingungen erfüllt und keine Multiplikation von zwei Elementen darin überläuft, kann dies im schlimmsten und besten Fall Theta(n-k)zeitlich und Theta(1)räumlich erfolgen.

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;

Dies ist hinsichtlich der asymptotischen Worst-Case-Komplexität sowohl für die Zeit als auch für den Raum optimal, da das optimale Produkt mindestens a[0]mit einem der n-(k+1)Elemente in der Entfernung vorliegen kann k+1, sodass mindestens n-(k+1)ganze Zahlen von jedem Algorithmus gelesen werden müssen, der das Problem löst.


Die Idee hinter dem Algorithmus ist wie folgt:

Das optimale Produkt verwendet zwei Elemente von a, vorausgesetzt, diese sind a[r]und a[s]. Ohne Verlust der Allgemeinheit können wir davon ausgehen, dass s > rdas Produkt kommutativ ist.

Aufgrund der Einschränkung abs(s-r) > kimpliziert dies, dass s >= k+1. Nun skönnte jeder der Indizes diese Bedingung erfüllen, also iterieren wir über diese Indizes. Dies ist die Iteration iim angezeigten Code, die jedoch der Einfachheit halber verschoben wird k+1(spielt keine Rolle). Für jede Iteration müssen wir das optimale Produkt mit i+k+1dem größten Index finden und es mit der vorherigen besten Schätzung vergleichen.

Die möglichen Indizes, i+k+1mit denen gepaart werden kann, sind iaufgrund der Abstandsanforderung alle Indizes kleiner oder gleich . Wir müssten auch alle diese Punkte durchlaufen, aber das ist unnötig, da das Minimum von a[i+k+1]*a[j]Over jbei Fix igleich min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))der Monotonie des Produkts entspricht (wobei das Minimum sowohl in Bezug auf das Minimum als auch das Maximum a[j]für die beiden möglichen berücksichtigt wird Zeichen a[i+k+1]oder gleichwertig die beiden möglichen Richtungen der Monotonie.)

Da die Menge der a[j]Werte, über die wir hier optimieren, gerade ist {a[0], ..., a[i]}und die einfach um ein Element ( a[i]) in jeder Iteration von wächst i, können wir einfach max(a[j])und min(a[j])mit einzelnen Variablen verfolgen , indem wir sie aktualisieren, wenn sie a[i]größer oder kleiner als die vorherigen optimalen Werte sind. Dies erfolgt mit back_maxund back_minim Codebeispiel.

Der erste Schritt der Iteration ( i=0) wird in der Schleife übersprungen und stattdessen als Initialisierung der Variablen ausgeführt.

Nussbaum
quelle
3
@greybeard Ich muss sie nicht behalten, weil die einzig möglichen Kandidaten für ein optimales Produkt mit a[i+k+1]dem Minimum und Maximum sind.
Walnuss
Können Sie erklären, warum der Algorithmus in Ihrer Antwort funktioniert?
MinaHany
6

Ich bin mir nicht sicher, ob ich am schnellsten bin .

Für das einfachere Problem ohne i <j - k gehört das Minimalprodukt zu den Produkten von Paaren aus den beiden kleinsten und größten Elementen.

Also (das Folgende ist zu kompliziert, siehe Walnuss-Antwort )
(• Hindernis, wenn k ≤ n
  • min initialisiereProdukt auf a [0] * a [k + 1])

  • Behalten Sie zwei dynamische Minmax-Datenstrukturen bei und jenseits von IplusK,
    beginnend mit {} und {a [ j ] | kj }
  • für jedes i von 0 bis n - k - 1
    • füge ein [ i ] zu upToI hinzu
    • entferne ein [ i + k ] von beyondIplusK
    • Suchen Sie nach einem neuen Minimalprodukt zwischen
      min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
      max ( upToI ) × min ( beyondIplusK ) und max ( upToI ) × max ( beyondIplusK ).
Graubart
quelle
Dies sollte zumindest in Bezug auf die Komplexität am schnellsten sein. Es ist O (n) Zeit und Speicher.
smttsp
Die ursprüngliche Lösung hat die Komplexität O (N ** 2). Wie schätzen Sie die Komplexität Ihrer Lösung ein?
Lenik
O (nlogn) Zeit, O (n) Raum (für geeignete Minmax-Implementierungen)
Graubart
@ Greybeard. Warum brauchst du keine Zeit? Warum nicht einfach einen 4 * n - Array zu halten , die enthält minUpto, maxUpto, minBeyond, maxBeyond(Sie in zwei Iterationen erstellen können)? Finden Sie dann in der dritten Iteration für jeden Index die minimal mögliche Multiplikation.
smttsp
(@smttsp Das wäre ein alternativer Schritt in Richtung sein Walnuss der Lösung .)
Greybeard
4

Für "minimale Größe"

Suchen Sie die 2 Elemente "kleinster Größe" und multiplizieren Sie sie (nachdem Sie entweder zwei Nullen gefunden oder das gesamte Array durchsucht haben).

Für "niedrigsten Wert" ohne das abs(i - j) > kTeil

Es gibt 3 Möglichkeiten:

  • die zwei höchsten (kleinste Größe) negativen Zahlen

  • die zwei niedrigsten (kleinste Größe) nicht negativen Zahlen

  • die niedrigste (größte Größe) negative Zahl und die höchste (größte Größe) nicht negative Zahl

Sie könnten nach allen 6 Werten suchen und die Produkte herausfinden, die am Ende am besten sind.

Jedoch; Sobald Sie eine Null sehen, wissen Sie, dass Sie nicht mehr über die ersten beiden Möglichkeiten Bescheid wissen müssen. und sobald Sie eine negative und eine nicht negative Zahl sehen, wissen Sie, dass Sie sich nur um die dritte Möglichkeit kümmern.

Dies führt zu einer endlichen Zustandsmaschine mit 3 Zuständen - "Sorge um alle 3 Möglichkeiten", "Antwort ist Null, es sei denn, eine negative Zahl wird gesehen" und "Sorge nur um die letzte Möglichkeit". Dies kann als ein Satz von 3 Schleifen implementiert werden, wobei 2 der Schleifen in ( goto) die Mitte einer anderen Schleife springen, wenn sich der Zustand (der endlichen Zustandsmaschine) ändert.

Insbesondere könnte es etwas vage aussehen (ungetestet):

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

Für "niedrigsten Wert" mit dem abs(i - j) > kTeil

In diesem Fall haben Sie noch die 3 Möglichkeiten; und könnte dazu führen, dass es mit dem gleichen Ansatz "3 Schleifen mit endlicher Zustandsmaschine" funktioniert, aber es wird zu chaotisch / hässlich. In diesem Fall ist es wahrscheinlich, dass eine bessere Alternative das Array vorab scannt, um festzustellen, ob Nullen vorhanden sind und ob alle negativ oder alle positiv sind. Damit Sie nach dem Pre-Scan entweder wissen, dass die Antwort Null ist, oder eine Schleife auswählen können, die nur für die jeweilige Möglichkeit ausgelegt ist.

Brendan
quelle
1
Wo erklärt dies die Untergrenze k der Indexdifferenz?
Graubart
1
@greybeard: Das tut es nicht (ich habe diesen Teil verpasst) - Code müsste geändert werden, um dies zu berücksichtigen.
Brendan
Warum brauchen Sie zwei Nullen?
TrentP
@TrentP: Argh - du hast recht. Eine Null reicht aus, um zu wissen, dass die Antwort entweder 0 oder eine negative Zahl ist.
Brendan