算法 如何取出一个数组中出现次数大于某个特定值的元素?

chucai · 2012年08月14日 · 最后由 mingyuan0715 回复于 2013年06月13日 · 5301 次阅读

前提条件,有一个数组 arr

arr = [1,2,1,3,4,5,3,4,5,3,2,9,8,3,5]

arr 的元素可以是任意 Integer 值,元素个数不定 如何取出 数组中 出现次数超过 5(或者 n)次的元素?

arr.select { |i| arr.count(i) > 5 }

arr.select { |i| arr.count(i) > 5 }.uniq

n = 2
arr.inject(Hash.new(0)) { |h, e| h[e] += 1; h }.select { |k, v| v > 2 }.keys

Update: 2 楼的更简洁:),不过效率可能这个更高些。

#2 楼 @fresh_fish 这个效率上怎么样?

#5 楼 @chucai 不知道,没试过

#5 楼 @chucai #6 楼 @fresh_fish O(n*n),如果 length 到千或万的规模会非常慢。

快排然后遍历一遍就可以了。

另一个 O(n) 的方法是用 group_by:

arr.group_by { |e| e }.select { |k, v| v.count > n }.keys

#9 楼 @ashchan 谢谢,给力!

#9 楼 @ashchan 如果再按出现次数排序用哪个方法啊。sort_by ?

需要 登录 后方可回复, 如果你还没有账号请 注册新账号