On vous donne un tableau (qui aura une longueur d'au moins trois, mais pourrait être très grand) contenant des entiers. La matrice est soit entièrement composée de nombres entiers impairs ou entièrement compris de même entiers, à l'exception d'un seul entier N. Écrivez une méthode qui prend la matrice comme argument et renvoie cette valeur aberrante N.
Ceci est mon code jusqu'à présent, ce qui ne 't semble fonctionner: Quel changement ai-je besoin avec ce code?
4 Réponses :
Voici un moyen simple de le faire group_by (&: impair?) fera 2 hachages pour les nombres impairs et paires < p> valeurs prendra les valeurs du hachage. 2 matrices, pour les paires et impair Sort_by (&: Comptez) Trier les matrices, une avec moins de valeurs sera la première [0] [0] saisir le premier numéro du premier tableau
Voici un algorithme de mémoire constant de temps linéaire
def find_outlier(ary)
# fetch first 3 numbers and determine what kind of array
# are we dealing with here, mostly odd or mostly even?
mostly_odd = ary.take(3).count(&:odd?) > 1
# then just go and find the outlier element
if mostly_odd
ary.find(&:even?)
else
ary.find(&:odd?)
end
end
ary = [161, 3, 1719, 19, 11, 160, 13, -21]
find_outlier(ary) # => 160
Undroted la réponse par demande de @sagarpandya
Voici une solution arcanique (laid), mais relativement simple. Il prend O ( Voici l'idée de base. Les chiffres même ont zéro pour le bit le moins significatif et les nombres impairs en ont une, donc si vous XOR une paire de nombres adjacente, le moindre bit le moins significatif ne sera qu'un seul si elle manque de parité. La première fois qui se produit après la première paire, vous avez trouvé l'aberrateur. Si cela se produit avec la première paire, vous devez vérifier le deuxième couplage. Si cela donne un zéro, la première valeur était la valeur aberrante, sinon c'était la seconde. P> et voici le même concept de manière légèrement plus rubisiste: p> arr.size code>) heure et utilise O (1) Stockage supplémentaire. Il "court-circuits" dès qu'il trouve l'aberrateur. Warming up --------------------------------------
cons3 bits: 128.000 i/100ms
cons2 bits: 127.000 i/100ms
cons2 even/odd: 103.000 i/100ms
find even/odd: 216.000 i/100ms
find bits: 217.000 i/100ms
find sergio: 231.000 i/100ms
Calculating -------------------------------------
cons3 bits: 1.251k (± 4.9%) i/s - 6.272k in 5.026355s
cons2 bits: 1.294k (± 3.4%) i/s - 6.477k in 5.010802s
cons2 even/odd: 1.038k (± 4.4%) i/s - 5.253k in 5.070617s
find even/odd: 2.284k (± 4.2%) i/s - 11.448k in 5.022831s
find bits: 2.165k (± 5.3%) i/s - 10.850k in 5.027801s
find sergio: 2.277k (± 3.3%) i/s - 11.550k in 5.078381s
Comparison:
find even/odd:: 2283.6 i/s
find sergio:: 2276.9 i/s - same-ish: difference falls within error
find bits:: 2164.6 i/s - same-ish: difference falls within error
cons2 bits:: 1294.2 i/s - 1.76x slower
cons3 bits:: 1251.1 i/s - 1.83x slower
cons2 even/odd:: 1038.1 i/s - 2.20x slower
N'est-ce pas chaque_cons (3) un peu gaspillé après les deux premières paires sont évaluées? Chaque paire sauf le premier et le dernier sera vérifié deux fois.
@Sergiotulentev Vous avez raison que cela ajoute plus de travail, mais sous la forme d'une constante scalaire, il ne modifie pas le comportement de Big-O. Je suis allé de l'avant et j'ai ajouté un contre (2) en fonction de votre commentaire. Un de ces jours, je vais devoir courir des timings pour voir si cela fait une différence notable.
HM, je pensais que la différence de performance serait plus prononcée. Merci!
Bienvenue dans le débordement de la pile!
Depuis que vous êtes nouveau, laissez-moi commencer par dire que demander des solutions ici n'est généralement pas bien reçu. Ce n'est pas un endroit où d'autres personnes font votre travail pour vous, vous devriez donc consulter https://stackoverflow.com / Aide / HOW-TO - Demandez pour en savoir plus sur ce qui fait une bonne question à l'avenir. P>
Cela dit, plutôt que de vous donner une solution, laissez-moi voir si je peux voir si je peux aider votre compréhension de ce qui semble vous trébucher. Je vais ignorer beaucoup de "ruby-isms" qui peut raccourcir beaucoup les choses, car ils sont gentils, mais il semble finalement que vous avez toujours besoin d'une compréhension de l'approche sous-jacente plutôt que de raccourcis, car c'est ce qui vous aide Programme Mieux à long terme. P>
if arr[i] == arr[j] count +=1 end
arr.first (3) .Count (&: impair?)> 1? arr.find (&: Même?): arr.find (&: impair?)Très pythonique! ;) À part les réponses que vous allez recevoir, faites une visite ici: Ruby- doc.org/core-2.6.1/array.html
Cela ressemble à un défi de Hackerrank ou de sites similaires. Est-ce?
@Sergio J'aimerais avoir gardé votre réponse à la hausse car elle donne une brève explication sur ce que le code fait et que vous donnez également le nom technique du processus.
@Sagarpandya: comme vous le souhaitez :)