2

With this code I can find most occurrences of items in an array:

letters.max_by { |i| letters.count(i) }

But this will return 2 for 

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

although 3 has the same occurrence. How can I find out, if there really is an item with most occurrences? I would like to get false if there is no single champion.

Asara
  • 2,791
  • 3
  • 26
  • 55
  • "Really" is not the right word for what you probably have in mind. – sawa Oct 30 '17 at 15:56
  • 1
    Possible duplicate of [Ruby: How to find item in array which has the most occurrences?](https://stackoverflow.com/questions/412169/ruby-how-to-find-item-in-array-which-has-the-most-occurrences) – Technophobe01 Oct 30 '17 at 20:01

4 Answers4

3

This is pretty ugly and in need of refinement, but:

def champion(array)
  grouped = array.group_by(&:itself).values.group_by(&:length)

  best = grouped[grouped.keys.max]

  if (best.length == 1)
    best[0][0]
  else
    false
  end
end

I'm not sure there's an easy single-shot solution for this, at least not one that's not O(n^2) or worse, which is unusual.

tadman
  • 208,517
  • 23
  • 234
  • 262
  • I know it's in the question, but it would be far more idiomatic to just return `best`. It should be up to the caller to check for 0, 1, or more maxima. – Max Oct 30 '17 at 16:29
  • @max Yeah, I don't disagree there. The design of this function could change considerably if the expectations are different. – tadman Oct 30 '17 at 16:38
1

I guess you could do this if you don't care about performance:

def max_occurrences(arr)
  arr.sort.max_by { |v| arr.count(v) } != arr.sort.reverse.max_by { |v| arr.count(v) } ? false : arr.max_by { |v| arr.count(v) }
end
Scott Schupbach
  • 1,284
  • 9
  • 21
Oli Crt
  • 1,123
  • 1
  • 11
  • 13
0

I would do something like this:

def max_occurrences(arr)
  counts = Hash.new { |h, k| h[k] = 0 }
  grouped_by_count = Hash.new { |h, k| h[k] = [] }
  arr.each { |el| counts[el] += 1 } # O(n)
  counts.each { |el, count| grouped_by_count[count] << el } # O(n)
  max = grouped_by_count.sort { |x, y| y[0] <=> x[0] }.first[1] # O(n log n)
  max.length == 1 ? max[0] : false
end

It's no snazzy one-liner, but it's readable and runs in less than O(n log n).

Scott Schupbach
  • 1,284
  • 9
  • 21
0
a = [1, 2, 2, 3, 3]
occurrences = a.inject(Hash.new(0)){ |h, el| h[el] += 1; h } # => {1=>1, 2=>2, 3=>2}
max_occurences = occurrences.max_by{ |_, v| v } # => [2, 2]
max_occurences.count > 1 ? false : occurrences.key(max_occurences.first)
vk26
  • 345
  • 3
  • 9