كيف يمكنني استخراج العناصر المتكررة بكفاءة في صفيف روبي؟ [مكرر

Question

هذا السؤال لديه بالفعل إجابة هنا:

• روبي: كيفية العثور على وإرجاع قيمة مكررة في الصفيف؟ 18 إجابة

لدي مجموعة مثل [1،1،1،2،4،6،3،3،3] وأرغب في الحصول على قائمة العناصر المتكررة، في هذه الحالة [1،3]. انا كتبت هذا:

my_array.select{|obj|my_array.count(obj)>1}.uniq

لكنه غير فعال بشكل مأساوي (O (N²)). هل تمتلك فكرة افضل؟ إذا كان ذلك ممكنا موجزة.

شكرًا

Answer 1

مستوحاة من إجابة إليا هايكينسون:

def repeated(array)
  counts = Hash.new(0)
  array.each{|val|counts[val]+=1}
  counts.reject{|val,count|count==1}.keys
end

Answer 2

باستخدام روبي جلس مكتبة:

require 'set'

ary = [1,1,1,2,4,6,3,3]
dups = Set.new
test_set = Set.new
ary.each {|val| dups.add(val) unless test_set.add?(val)}
dups.to_a # [1, 3]

أعتقد أن هذا يجب أن يكون O (n)، لأن مجموعة # إضافة وتعيين # إضافة؟ هي عمليات ثابتة، بقدر ما أعرف.

Answer 3

ماذا عن شيء مثل هذا؟ سوف يعمل في O (ن).

a = [1,1,1,2,4,6,3,3]
b = {}
a.each { |v| if b.has_key? v then b[v] = b[v]+1 else b[v]=1 end }
b.reject { |k,v| if v > 1 then false else true end }.keys

Answer 4

حل AO (N) (تغيير << x ل + [x] و update ل merge لجعلها وظيفية بحتة):

rs = xs.inject([[], {}]) do |(out, seen), x| 
  [(seen[x] == 1 ? (out << x) : out), seen.update(x => (seen[x] || 0)+1)]
end[0]

نهج أكثر بساطة بعد أقل كفاءة فضائية:

rs = xs.group_by { |x| x }.select { |y, ys| ys.size > 1 }.keys

نفس الفكرة تجنب التجزئة الوسيطة باستخدام "فهم قائمة":

rs = xs.group_by { |x| x }.map { |y, ys| y if ys.size > 1 }.compact

Answer 5

استخدام inject

[1,1,1,2,4,6,3,3].inject({}){ |ele, n| ele[n] = nil; ele }.keys 
# => [1, 2, 4, 6, 3] 

تفسير:

ele التجزئة تم تخصيصها {}, ، كل تكرار مفتاح مع الرقم n و nil تتم إضافة القيمة إلى ele التجزئة. في نهايةالمطاف ele يتم إرجاع كما:

{1=>nil, 2=>nil, 4=>nil, 6=>nil, 3=>nil}

نريد فقط المفاتيح، لذلك .keys ينتهي الوظيفة.

Answer 6

بعض الأفكار: يجب عليك معرفة هياكل بيانات المكتبة الصحيحة:

1 فرز الصفيف O (NLGON)، ثم تشغيل الصفيف

2 قم بإنشاء مجموعة، والبحث عن عنصر الصفيف الحالي في المجموعة وإذا لم يتم العثور عليه، وإدراج ومتابعة لجميع العناصر - O (NLGON) مرة أخرى.

Answer 7

كنت أفكر في حساب عدد المرات التي تظهر عنصر فريد في الصفيف. قد يكون ذلك غير فعال حقا تماما مثل الاقتراح الأصلي ولكنه كان ممتعا بالنظر إلى المشكلة. لم أفعل أي معايير على صفائف أكبر، لذلك هذا مجرد تمرين.

a = [1,1,1,2,4,6,3,3]

dupes = []
a.uniq.each do |u|
  c = a.find_all {|e| e == u}.size
  dupes << [u, c] unless c == 1
end

puts dupes.inspect

# dupes = [[1, 3], [3, 2]]
# 1 appears 3 times
# 3 appears twice


# to extract just the elment a bit cleaner
dupes = a.uniq.select do |u|
  a.find_all {|e| e == u}.size != 1
end
puts dupes.inspect
# returns [1,3]

Answer 8

سيعمل ذلك إذا كانت الإدخالات المكررة متتالية دائما، كما هو الحال في مثالك؛ وإلا سيكون عليك الترتيب أولا. كل_cons يفحص نافذة المتداول بالحجم المحدد.

require 'set'

my_array = [1,1,1,2,4,6,3,3]
dups = Set.new
my_array.each_cons(2) {|a,b| dups.add(a) if (a == b)}
p dups.to_a