Plage minimum de 3 jeux

Question

Nous avons trois jeux S1, S2, S3. Je besoin de trouver x, y, z de telle sorte que x E S1 y E S2 z E S3

laisse min désignent la valeur minimum de x, y, z let max désignent la valeur maximale de x , y, z la gamme notée max-min doit être la valeur minimale possible

Answer 1

min = infinity (really large number in practice, like 1000000000) 
solution = (-, -, -) 
for each x E S1 
    for each y E S2 
     for each z E S3 
      t = max(x, y, z) - min(x, y, z) 
      if t < min 
       min = t 
       solution = (x, y, z) 

Answer 2

Bien sûr, la solution complète bruteforce décrite par IVlad est simple et, par conséquent, plus facile et plus rapide à écrire, mais il est la complexité est O(n3).

Selon votre balise algorithm, je voudrais poster un algorithme plus complexe, qui a un O(n2) pire des cas et O(nlogn) complexité moyenne (presque sûr à ce sujet, mais je suis trop paresseux pour faire une preuve).

Description de l'algorithme

Pensez à penser à une abstraite (X, Y, Z) tuple. Nous voulons trouver un tuple qui a une distance minimale de entre son élément maximum et minimum. Ce que nous pouvons dire à ce stade est que la distance est en fait créée par notre élément maximum et élément minimum. Par conséquent, la valeur de l'élément entre eux n'a vraiment aucune importance tant qu'elle se situe vraiment entre le maximum et le minimum.

Donc, voici l'approche. Nous allouons un ensemble supplémentaire (appelons-le S) et combinons chaque ensemble initial (X, Y, Z) en un seul. Nous avons également besoin d'une possibilité de rechercher le initial ensemble de chaque élément de l'ensemble que nous venons de créer (donc, si nous désignons un élément dans S, disons S[10] et demandons "D'où vient ce type?", notre application devrait répondre à quelque chose comme « il vient de Y).

Après cela, nous allons trier notre nouvelle série S par ses clés (ce serait O (n log n) ou O (n) certains cas)

Déterminer la mini mal la distance

Maintenant, la partie intéressante vient. Ce que nous voulons faire est de calculer une valeur artificielle, appelons-le distance minimale et le marquer comme d[x], où x est un élément de S. Cette valeur fait référence à la distance minimale max - min qui peut être atteinte en utilisant les éléments qui sont les prédécesseurs/successeurs de l'élément courant dans la séquence.

Prenons l'exemple suivant - ceci est notre S set (première ligne montre des index, des secondes - des valeurs et des lettres X, Y et Z font référence à des ensembles initiaux):

0 1 2 3 4 5 6 7 
------------------ 
1 2 4 5 8 10 11 12 
Y Z Y X Y Y X Z 

Disons que nous voulons calculer que notre distance minimale pour l'élément avec l'index 4.En fait, cette distance minimale signifie meilleur(x, y, z) tuple qui peut être construit en utilisant l'élément sélectionné.

Dans notre cas (S[4]), nous pouvons dire que notre (x, y, z) paire ressemblerait certainement comme (something, 8, something), car il doit avoir l'élément que nous comptons la distance pour (assez évident, hehe).

Maintenant, nous devons combler les lacunes. Nous savons que les éléments que nous recherchons, devraient être de X et Z. Et nous voulons que ces éléments soient le meilleur en termes de distance max - min. Il existe un moyen facile de les sélectionner.

Nous effectuons une exécution bidirectionnelle (exécution à gauche, exécution à partir de l'élément actuel) en recherchant le premier élément-non-à partir de Y. Dans ce cas, nous chercherions deux éléments les plus proches de X et Z dans deux directions (4 éléments au total).

Cette méthode de recherche est ce que nous avons besoin: si nous choisissons le premier élément de X lors de l'exécution (gauche/droite, n'a pas d'importance), cet élément costume nous mieux que tout autre élément qui le suit dans termes de distance. Cela se produit parce que notre jeu S est trié.

En cas de mon exemple (en comptant la distance pour l'élément avec le numéro d'index 4), nous marquerait des éléments avec des indices 6 et 7 comme appropriée du côté droit et des éléments avec des indices 1 et 3 du côté gauche.

Maintenant, nous devons tester 4 cas qui peuvent arriver - et prendre le cas pour que notre distance soit minimale. Dans notre cas particulier, nous avons les suivants (éléments retournés par la routine précédente):

Z X Y X Z 
2 5 8 11 12 

Nous devons tester tous les (X, Y, Z) tuple qui peut être construit en utilisant ces éléments, prendre la tuple avec la distance minimale et gardez cette distance pour notre élément. Dans cet exemple, nous dirions que (11, 8, 12) tuple a la meilleure distance de 4. Donc, nous stockons d[5] = 4(5 voici l'index de l'élément).

Cédant le résultat

Maintenant, quand on sait comment trouver la distance, nous allons le faire pour chaque élément dans notre S ensemble (cette opération prendrait O(n2) dans le pire des cas et un meilleur temps - quelque chose comme O(nlogn) en moyenne).

Après nous avons cette valeur de distance pour chaque élément dans notre jeu, il suffit de sélectionner l'élément avec distance minimale et exécuter notre la distance de comptage algorithme (qui est décrit ci-dessus) pour une fois de plus, mais maintenant enregistrer le (-, -, -) tuple. Ce serait la réponse.

pseudocode

Voici vient le pseudocode, j'ai essayé de le rendre facile à lire, mais il est la mise en œuvre serait plus complexe, car vous aurez besoin de coder lookups set * («déterminer fixé pour l'élément "). Notez également que déterminer les tuple et déterminer les routines de distance sont fondamentalement les mêmes, mais la seconde donne le tuple réel.

COMBINE (X, Y, Z) -> S 
SORT(S) 

FOREACH (v in S) 
    DETERMINE_DISTANCE(v, S) -> d[v] 

DETERMINE_TUPLE(MIN(d[v])) 

P.S

Je suis assez sûr que cette méthode pourrait être facilement utilisé pour (-, -, -, ... -) recherche tuple, ce qui encore une bonne complexité algorithmique.