Comment puis-je supprimer efficacement les doublons négatifs d'entiers positifs d'un tableau d'entiers positifs et négatifs comme celui-ci: [1, 5, 10, 5, -5, -1, 9] en conséquence, je veux avoir: [1, 5, 10, 5, 9] (-1 et -5 supprimés car ce sont des doublons négatifs de 1 et 5)

4
Evanto 24 janv. 2017 à 22:34

5 réponses

Meilleure réponse

C'est la méthode la plus simple que j'ai pu trouver:

  • sélectionner des nombres positifs
  • calculer leur nombre opposé
  • supprimez-les de la matrice d'origine

array = [1, 5, 10, 5, -5, -1, 9]

p array - array.select{ |i| i > 0 }.map{ |i| -i }
# [1, 5, 10, 5, 9]

Il utilise Array#-, qui devrait être raisonnablement rapide.

6
Eric Duminil 24 janv. 2017 à 21:58

Dans Ruby, vous pouvez utiliser la méthode uniq: https: / /ruby-doc.org/core-2.2.0/Array.html#method-i-uniq.

Sinon, vous voudrez vérifier une réponse comme celle-ci qui explique comment créer une structure pour parcourir un tableau.

0
Community 23 mai 2017 à 11:46

Vous pouvez le faire facilement en utilisant le rejet de tableau:

>> a = [1, 5, 10, 5, -5, -1, 9]
>> a.reject { |e| e < 0 && a.include?(e.abs) }
=> [1, 5, 10, 5, 9]

Pour clarifier avec un autre exemple, cela ne supprimera pas les valeurs négatives qui n'ont pas de valeur positive correspondante dans le tableau:

>> b = [1, 5, 10, 5, -5, -1, 9, -15]
>> b.reject { |e| e < 0 && b.include?(e.abs) }
=> [1, 5, 10, 5, 9, -15]

Vous pouvez définir une méthode comme ceci:

def reject_negative_duplicates(array)
  array.reject { |e| e < 0 && array.include?(e.abs) }
end

>> reject_negative_duplicates(a)
=> [1, 5, 10, 5, 9]
>> reject_negative_duplicates(b)
=> [1, 5, 10, 5, 9, -15]

Ou étendre (monkey patch) Array:

class Array
  def reject_negative_duplicates
    self.reject { |e| e < 0 && self.include?(e.abs) }
  end
end

>> a.reject_negative_duplicates
=> [1, 5, 10, 5, 9]
>> b.reject_negative_duplicates
=> [1, 5, 10, 5, 9, -15]
4
moveson 27 févr. 2017 à 20:36
arr = [1, 5, 10, 0, 5, -5, -1, 9, -4]

arr - arr.each_with_object([]) { |n,b| b << -n if n > 0 }
  #=> [1, 5, 10, 0, 5, 9, -4] 
3
Cary Swoveland 25 janv. 2017 à 02:10

Vous pouvez le faire dans O(n) avec seulement deux passages dans le tableau en hachant les nombres positifs puis en rejetant du tableau les valeurs négatives dont les abs ont été hachés:

def reject_neg_dups(arr)
  positives = Hash[arr.map {|x| (x>0) ? [x,1] : nil }.compact]
  arr.reject { |x| (x < 0) && positives[-x] }
end

reject_neg_dups([-1, 1, 2, -2]) # => [1, 2]
reject_neg_dups([-1, 1, -2]) # => [1, -2] since 2 does not appear

Il est intéressant de noter que les Array- solutions sont considérablement plus rapides que les autres répertoriées jusqu'à présent:

require 'benchmark'

def reject_neg_dups_hash(arr)
  positives = Hash[arr.map {|x| (x>0) ? [x,1] : nil }.compact]
  arr.reject { |x| (x < 0) && positives[-x] }
end

def reject_neg_dups_include(arr)
  arr.reject { |x| (x < 0) && arr.include?(x.abs) }
end

def reject_neg_dups_arrayminus(arr)
  arr - arr.select { |i| i > 0 }.map { |i| -i }
end

def reject_neg_dups_arrayminusewo(arr)
  arr - arr.each_with_object([]) { |n,b| b << -n if n > 0 }
end

arr = Array.new(1000) { rand(-100..100) }
N = 1000
Benchmark.bm(15) do |x|
  x.report('Array-')    { N.times { reject_neg_dups_arrayminus(arr.dup) } }
  x.report('Array-ewo') { N.times { reject_neg_dups_arrayminusewo(arr.dup) } }
  x.report('hash')      { N.times { reject_neg_dups_hash(arr.dup) } }
  x.report('include?')  { N.times { reject_neg_dups_include(arr.dup) } }
end

Exemple de sortie:

                      user     system      total        real
Array-            0.180000   0.000000   0.180000 (  0.187512)
Array-ewo         0.200000   0.000000   0.200000 (  0.194663)
hash              0.250000   0.010000   0.260000 (  0.253355)
include?          3.660000   0.000000   3.660000 (  3.666313)
5
Community 23 mai 2017 à 12:10