produit de deux nombres dans un tableau

Étant donné un tableau de n entier distinct. Trouver toutes les paires de x, y dans le tableau tel que z (donné) = x * y ... le faire sans tri et de la manière la plus efficace ..produit de deux nombres dans un tableau

[edit] Les nombres entiers sont dans la plage de int ie 0 -65536 et les nombres ne sont pas négatifs si cela aide. Ne pas vouloir trier car cela prendra beaucoup de temps. L'espace de stockage n'est pas un problème.

Source

2010-12-08 ashmish2

et votre question est? – birryree

se lit comme des devoirs ... –

Je n'aime pas les questions avec des contraintes comme "ne pas utiliser le tri", "ne pas utiliser les boucles" ...: - \ – st0le

Voici une solution basée sur hachage de temps linéaire:

Let hash be an array of size 65537 initilized to 0. 

foreach element ele in Array 

    if ele != 0 
     hash[product/ele] = ele 
    end-if 

    if hash[ele] != 0 AND ele * hash[ele] == product 
     print ele, product/ele 
    end-if 

end-foreach

Source

2010-12-08 05:56:10 codaddict

La deuxième boucle peut être fusionnée en le premier ... je pense. aussi cela imprimera à la fois 'a * b' et' b * a' .... – st0le

@stOle: Merci d'avoir choisi. l'impression de paires distinctes est laissée comme HW pour OP. – codaddict

merci codaddict ça a l'air bien – ashmish2

Il n'y a pas de moyen très efficace de le faire. Le meilleur que je peux penser est O (n^2):

Avoir une fonction auxiliaire qui prend un nombre (a) et une liste, et passe par chaque élément (b) vérifier un * b = z et enregistrer le paire si c'est le cas. Parcourez tous les éléments de votre liste d'origine, et si un élément particulier (x) divise z (ie z% x = 0), envoyez x et le reste de la liste après x à la fonction auxiliaire.

MISE À JOUR:

Je donne une solution O (n^2) parce que la question n'a pas précisé uniques paires. Si seulement des paires uniques sont désirées, ceci devrait être ajouté à la question. Aussi, ma solution suppose que l'ordre des paires n'a pas d'importance, ce qui est un autre détail qui devrait être clarifié.

Source

2010-12-08 05:51:52

Non o (n^2) est hors de question. Je vais préférer trier plutôt que faire ça. – ashmish2

le tableau contient des entiers distincts, donc évidemment, les paires seront uniques .... – st0le

@ st0le vous avez absolument raison, je ne devrais pas avoir critiqué le libellé sans réellement le lire attentivement d'abord –

Itérer à travers le réseau ... si un élément x peut diviser z (c.-à-z % x == 0), vérifier si elle est autre facteur y=(z/x) existe dans le Hashtable ....

Si oui, alors vous avez trouvé une paire ... autre il suffit d'ajouter à la table de hachage et continuer ...

Source

2010-12-08 05:53:55 st0le

Répondre

Questions connexes