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

13

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?

Mouvre
la source
7
Pourquoi ne devrais-je pas #inclure <bits / stdc ++. H>? et C ++ fournissent uniquement un tableau de longueur variable par extension de compilateur. Pourquoi n'utilisez-vous pas std::vector? @Scheff - le tri détruirait les relations "de distance" d'origine.
David C. Rankin
3
Au moins, le contrôle if (i!=j) if (abs(i - j) > k)peut être éliminé. Il suffit de commencer la boucle interne à i + k + 1: for (ll j = i + k + 1; j < n; ++j). Le chèque avec firstpeut également être éliminé s'il mnest initialisé avant, par exemple avec mn = a[0] * a[k + 1];. (Peut-être, kdevrait être vérifié au ndépart pour rendre ce pare-balles.) Mais c'est toujours O (N²). Cela doit être faisable plus rapidement ...
Scheff
2
@PaulMcKenzie Veuillez afficher une requête avec pas moins de deux résultats utiles parmi les dix premiers pour un produit minimal avec une distance d'index (ou maximale).
greybeard
1
@PaulMcKenzie "Il y a probablement des centaines, voire des milliers de liens URL qui montrent les réponses à cette question." - veuillez partager au moins trois de ces URL.
גלעד ברקן
2
D'où vient cette question? Cela ne ressemble pas à quelque chose composé uniquement d'air mince. Je ne serais pas surpris s'il provenait de l'un de ces sites "juge en ligne". Si c'est le cas, sur ces sites, il y a probablement de longues discussions sur la résolution du problème, sinon des solutions complètes.
PaulMcKenzie

Réponses:

12

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.

noyer
la source
3
@greybeard Je n'ai pas besoin de les garder, car les seuls candidats possibles pour un produit optimal a[i+k+1]sont le minimum et le maximum.
noyer
pourriez-vous expliquer pourquoi l'algorithme fonctionne dans votre réponse?
MinaHany
6

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 ] | kj }
  • 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 )
gris barbe
la source
Ce devrait être le plus rapide, du moins en termes de complexité. C'est le temps O (n) et le stockage.
smttsp
la solution d'origine a la complexité O (N ** 2), comment estimez-vous la complexité de votre solution?
lenik
Temps O (nlogn), espace O (n) (pour les implémentations minmax appropriées)
barbe grise
@vieil homme. Pourquoi avez-vous besoin d'un temps de connexion n *. Pourquoi ne pas garder simplement un tableau 4 * n qui contient minUpto, maxUpto, minBeyond, maxBeyond(Vous pouvez créer en deux itérations)? Ensuite, dans la troisième itération, pour chaque index, trouvez la multiplication minimale possible.
smttsp
(@smttsp Ce serait une étape alternative dans la direction de la solution de noyer .)
greybeard
4

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.

Brendan
la source
1
Où cela explique-t-il la borne inférieure k sur la différence d'indice?
greybeard
1
@greybeard: Ce n'est pas le cas (j'ai raté cette partie) - le code devrait être modifié pour en tenir compte.
Brendan
Pourquoi auriez-vous besoin de deux zéros?
TrentP
@TrentP: Argh - vous avez raison. Un zéro suffit pour savoir que la réponse est soit 0, soit un nombre négatif.
Brendan