6

[1,1,1,2,4,6,3,3] のような配列があり、この場合は [1,3] の繰り返し要素のリストを取得したいと考えています。私はこれを書きました:

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

しかし、それは悲劇的に非効率的です (o(n²))。もっと良いアイデアはありますか?できれば簡潔に。

ありがとう

4

8 に答える 8

9

イリヤ・ヘイキンソンの答えに触発されました:

def repeated(array)
  counts = Hash.new(0)
  array.each{|val|counts[val]+=1}
  counts.reject{|val,count|count==1}.keys
end
于 2009-04-24T18:49:26.680 に答える
6

Ruby のSetライブラリを使用する:

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]

Set#add と Set#add? 私の知る限り、一定時間の操作です。

于 2009-04-24T18:09:02.083 に答える
4

このようなものはどうですか?O(n)で実行されます。

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
于 2009-04-24T18:34:31.910 に答える
3

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
于 2011-12-10T19:00:26.390 に答える
1

使用するinject

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

説明:

eleハッシュに初期化され、各反復で数値と値{}を含むキーがハッシュに追加されます。最後に次のように返されます。nnileleele

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

キーだけが必要なので.keys、作業は終了です。

于 2013-07-19T18:59:23.387 に答える
0

一意の要素が配列に何回出現するかを数えることを考えていました。元の提案と同じように非常に非効率的かもしれませんが、問題を見るのは楽しかったです。大規模なアレイでベンチマークを行っていないため、これは単なる演習です。

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]
于 2009-12-18T06:05:22.127 に答える
0

これは、例のように、重複したエントリが常に連続している場合に機能します。そうしないと、最初にソートする必要があります。each_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
于 2009-12-18T06:45:20.317 に答える
0

いくつかのアイデア: 正しいライブラリ データ構造を把握する必要があります。

1配列 O(nlogn) をソートし、配列全体を実行します

2セットを作成し、セット内の現在の配列要素を検索し、見つからない場合はすべての要素を挿入して続行します -- O(nlogn) 再び。

于 2009-04-24T17:45:17.443 に答える