Reputation: 89
How to return the third largest number in an array
My code logic to answer a programming question is:
- Find the biggest number in the input array.
- Store that number in a new array.
- Delete that number from the input array.
- Repeat #'s 1-3 until I have three elements in the new array.
- Choose the last element of the array to return.
My code is returning three 10's, instead of the three largest elements in the array, 10, 8, and 4. I think it might be because once the inner while loop is done, the code cannot return back to it?
My test code is:
puts(third_greatest([8, 1, 10, 4])).to_s
My code is:
def third_greatest(nums)
greatest_number = nil
three_greatest = []
three_greatest_idx = 0
while three_greatest_idx < 3
number_idx = 0
while number_idx < nums.length
current_number = nums[number_idx]
if greatest_number == nil
greatest_number = current_number
elsif greatest_number < current_number
greatest_number = current_number
end
number_idx += 1
end
three_greatest.unshift(greatest_number)
nums.delete(greatest_number)
three_greatest_idx += 1
end
return three_greatest
end
Upvotes: 3
Views: 2286
Answers (5)
Reputation: 8513
Sort it and use Ruby's negative index option for arrays.
[8, 1, 10, 4].sort[-3]
>> 4
Edit: After many tests I have determined that the sort method shown above is faster than the method below if, when searching for the nth biggest number in an array of m elements, n > 1/20th the size of m. Since in your example we are looking for the 3rd biggest number in an array of 4 elements, and 3 is much bigger than .2, the answer above is significantly more efficient than this alternative method:
[8, 1, 10, 4].max(3)[-1]
>> 4
Upvotes: 1
Reputation: 160551
Just to help people understand the difference in performance between max, sort and not using built-in methods:
require 'fruity'
ary = (1..100).to_a.shuffle
def use_max(a)
a.max(3).last
end
def use_sort(a)
a.sort[-3]
end
def nth_greatest(nums, n)
nums = nums.dup # prevent mutating the original array
result = nil
n.times do
idx, max = -1, -Float::INFINITY
nums.length.times do |i|
idx, max = [i - 1, nums[i - 1]] if nums[i - 1] > max
end
result = nums.delete_at idx
end
result
end
compare do
sorted { use_sort(ary) }
maxed { use_max(ary) }
nth_greatested { nth_greatest(ary, 3) }
end
# >> Running each test 512 times. Test will take about 1 second.
# >> sorted is faster than maxed by 2x ± 0.1
# >> maxed is faster than nth_greatested by 3x ± 0.1
Increasing the size of the array:
ary = (1..1_000).to_a.shuffle
results in:
# >> Running each test 64 times. Test will take about 1 second.
# >> maxed is faster than sorted by 80.0% ± 10.0%
# >> sorted is faster than nth_greatested by 3x ± 0.1
And bumping up the array size again:
ary = (1..10_000).to_a.shuffle
results in:
# >> Running each test 8 times. Test will take about 1 second.
# >> maxed is faster than sorted by 3x ± 0.1
# >> sorted is faster than nth_greatested by 2x ± 0.1
The documentation doesn't mention if max(3) returns a reversed sorted array, even though it looks like it.
The documentation example is:
a.max(2) #=> ["horse", "dog"]
which is descending, but that's not a good example as it's easier to see using numbers:
ary.max(3) # => [100, 99, 98]
Here are some results using Benchmark to show the baseline speeds:
require 'benchmark'
ary = (1..5).to_a.shuffle
10.times do
Benchmark.bm(4) do |b|
b.report('sort') { ary.sort[-3] }
b.report('max') { ary.max(3).last }
end
end
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000010)
# >> max 0.000000 0.000000 0.000000 ( 0.000006)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000004)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000004)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000003)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000004)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000004)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000005)
# >> max 0.000000 0.000000 0.000000 ( 0.000005)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000004)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000003)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000003)
# >> max 0.000000 0.000000 0.000000 ( 0.000003)
And increasing the size of the array:
ary = (1..100).to_a.shuffle
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000020)
# >> max 0.000000 0.000000 0.000000 ( 0.000013)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000013)
# >> max 0.000000 0.000000 0.000000 ( 0.000011)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000010)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000009)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000009)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000008)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000008)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000008)
# >> max 0.000000 0.000000 0.000000 ( 0.000013)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000011)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000008)
# >> max 0.000000 0.000000 0.000000 ( 0.000010)
And:
ary = (1..1_000).to_a.shuffle
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000110)
# >> max 0.000000 0.000000 0.000000 ( 0.000057)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000103)
# >> max 0.000000 0.000000 0.000000 ( 0.000054)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000101)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000100)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000100)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000100)
# >> max 0.000000 0.000000 0.000000 ( 0.000056)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000099)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000099)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000100)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
# >> user system total real
# >> sort 0.000000 0.000000 0.000000 ( 0.000099)
# >> max 0.000000 0.000000 0.000000 ( 0.000053)
Upvotes: 6
Reputation: 30056
You forgot to unset greatest_number
nums.delete(greatest_number)
three_greatest_idx += 1
greatest_number = nil # this line
end
Obviously there is a very simple solution for this in Ruby but I took for granted that you wanted to do it on your own.
Upvotes: 3
Reputation: 121000
I assume this is a task where heavy usage of Enumerable module might be not permitted. There are still easier approaches all around. E.g. you do not need to maintain another array: just remove the highest from the original array N times:
def nth_greatest(nums, n)
nums = nums.dup # prevent mutating the original array
result = nil
n.times do
idx, max = -1, -Float::INFINITY
nums.length.times do |i|
idx, max = [i - 1, nums[i - 1]] if nums[i - 1] > max
end
result = nums.delete_at idx
end
result
end
nth_greatest [8, 1, 10, 4], 2
#⇒ 8
nth_greatest [8, 1, 10, 4], 3
#⇒ 4
Upvotes: 2
Reputation: 211560
Once you start to think about solving problems like this the Ruby way, by which I mean leaning more heavily on Enumerable and expressing your intent as a series of simple operations, often chained together, then the solutions become easier to find.
For example, to find the three highest numbers in an arbitrary Array the obvious solution might be this:
def three_greatest(list)
list.sort.reverse.first(3)
end
That sorts the list, which by default is lowest to highest, and then reverses it, making it highest to lowest. The last operation is to copy out the first three entires. This seems pretty reasonable, as it expresses your intent quite clearly and works quite well.
The thing is if you look more closely at the Enumerable offerings there's an even easier solution using max:
def three_greatest(list)
list.max(3)
end
The lesson to learn here is that the Enumerable library, not unlike a mechanic's tool-chest, has a very large number of useful tools. It's important to take some time to at least read through what's in there so you don't end up wasting time re-inventing things that already exist in an elegant form.
In other words, when tackling a problem, check to see if that problems already been solved. In many cases you'll find there's a tool that does exactly what you're looking for.
Upvotes: 12
Related Questions
- How can I find the index of the second greatest element in my array?
- Find second largest number from an array in Ruby
- How to generate or create the largest number from a given array using ruby
- returning the second highest value in an array - ruby
- Finding the value and index of the first occurence of the largest element in an array
- Get variable whose value is the maximum in an array
- How can I find the max value from an array of arrays?
- Find largest element from multidimensional array of ints
- Ruby Array - highest integer
- How do I find a integer/max integer in an array for ruby and return the indexed position?