Le moyen le plus rapide de trouver un produit minimal de 2 éléments de tableau contenant 200 000+ éléments

J'ai un tableau a[n]. Nous saisissons le numéro n. J'ai besoin de trouver le produit minimal a[i]et a[j]si:

1) abs(i - j) > k

2) a[i] * a[j]est minimisé

Voici ma solution (très naïve):

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

Mais je veux savoir s'il existe un moyen plus rapide de trouver un produit minimal à distance?

En supposant qu'il y ait au moins une paire d'éléments satisfaisant aux conditions et qu'aucune multiplication de deux éléments ne déborde, cela peut être fait dans le pire et le meilleur des cas dans le Theta(n-k)temps et l' Theta(1)espace, avec quelque chose comme ceci:

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;

C'est optimal en termes de complexité asymptotique dans le pire des cas, à la fois dans le temps et dans l'espace, car le produit optimal peut être a[0]avec au moins l'un des n-(k+1)éléments à distance k+1, donc au moins les n-(k+1)entiers doivent être lus par tout algorithme résolvant le problème.

L'idée derrière l'algorithme est la suivante:

Le produit optimal utilise deux éléments de a, supposons que ce soient a[r]et a[s]. Sans perte de généralité, nous pouvons supposer que s > rpuisque le produit est commutatif.

En raison de la restriction, abs(s-r) > kcela implique que s >= k+1. Maintenant, schacun des indices pourrait satisfaire à cette condition, donc nous itérons sur ces indices. C'est l'itération idans le code affiché, mais elle est décalée k+1pour plus de commodité (peu importe). Pour chaque itération, nous devons trouver le produit optimal impliquant i+k+1le plus grand indice et le comparer avec la meilleure estimation précédente.

Les indices possibles à coupler i+k+1sont tous des indices plus petits ou égaux en iraison de la distance requise. Nous aurions besoin d'itérer sur tous ces éléments également, mais cela n'est pas nécessaire car le minimum de a[i+k+1]*a[j]sur jà fixe iest égal à en min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))raison de la monotonie du produit (en prenant le minimum en ce qui concerne à la fois le minimum et le maximum sur les a[j]comptes pour les deux possibles signes a[i+k+1]ou équivalents des deux directions possibles de la monotonie.)

Puisque l'ensemble de a[j]valeurs sur lesquelles nous optimisons ici est juste {a[0], ..., a[i]}, qui croît simplement d'un élément ( a[i]) à chaque itération de i, nous pouvons simplement garder une trace de max(a[j])et min(a[j])avec des variables uniques en les mettant à jour si elles a[i]sont plus grandes ou plus petites que les valeurs optimales précédentes. Cela se fait avec back_maxet back_mindans l'exemple de code.

La première étape de l'itération ( i=0) est ignorée dans la boucle et effectuée à la place comme initialisation des variables.

Je ne sais pas trop vite .

Pour le problème plus simple sans i <j - k , le produit minimal est parmi les produits des paires des deux éléments les plus petits et les plus grands.

Donc, (ce qui suit est trop compliqué, voir la réponse de Walnut )
(• rechigner si k ≤ n
  • initialiser minProduct à a [0] * a [k + 1])

• garder deux structures de données minmax dynamiques upToI et beyondIplusK
  commençant par {} et {a [ j ] | k ≤ j }
• pour chaque i de 0 à n - k - 1
  • ajouter un [ i ] à upToI
  • supprimer un [ i + k ] de BeyondIplusK
  • rechercher un nouveau produit minimal parmi
    min ( upToI ) × min ( BeyondIplusK ), min ( upToI ) × max ( BeyondIplusK ),
    max ( upToI ) × min ( BeyondIplusK ) et max ( upToI ) × max ( BeyondIplusK )

Pour "magnitude minimale"

Trouvez les 2 éléments de "plus petite amplitude", puis (après avoir trouvé deux zéros ou fouillé l'ensemble du tableau), multipliez-les.

Pour la "valeur la plus basse" sans abs(i - j) > k pièce

Il y a 3 possibilités:

• les deux nombres négatifs les plus élevés (la plus petite ampleur)

• les deux nombres non négatifs les plus bas (de plus petite ampleur)

• le nombre négatif le plus bas (la plus grande ampleur) et le nombre non négatif le plus élevé (la plus grande ampleur)

Vous pouvez rechercher les 6 valeurs et déterminer les produits et ce qui est le mieux à la fin.

Toutefois; dès que vous voyez un zéro, vous savez que vous n'avez plus besoin d'en savoir plus sur les 2 premières possibilités; et dès que vous voyez un nombre négatif et un nombre non négatif, vous savez que vous ne vous souciez que de la troisième possibilité.

Cela conduit à une machine à états finis avec 3 états - "se soucie de toutes les 3 possibilités", "la réponse est zéro à moins qu'un nombre négatif ne soit vu" et "ne se soucie que de la dernière possibilité". Cela peut être implémenté comme un ensemble de 3 boucles, où 2 des boucles sautent dans ( goto) le milieu d'une autre boucle lorsque l'état (de la machine à états finis) change.

Plus précisément, cela pourrait ressembler à quelque chose de vaguement (non testé):

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

Pour "valeur la plus basse" avec la abs(i - j) > kpièce

Dans ce cas, vous avez encore les 3 possibilités; et pourrait le faire fonctionner avec la même approche "3 boucles avec machine à états finis" mais cela devient trop désordonné / moche. Dans ce cas, une meilleure alternative est susceptible de pré-scanner le tableau pour déterminer s'il y a des zéros et s'ils sont tous négatifs ou tous positifs; de sorte qu'après le pré-scan, vous pouvez savoir que la réponse est zéro ou sélectionner une boucle conçue pour la seule possibilité spécifique.