All geek questions in one place

How to return the third largest number in an array

My code logic for answering a programming question:

  • Find the largest number in the input array.
  • Store this number in a new array.
  • Remove this number from the input array.
  • Repeat # 1-3 until I have three elements in a new array.
  • Select the last element of the returned array.

My code returns three ten, not the three largest elements in the array, 10, 8, and 4. I think it could be because once the inner loop is executed, the code will not be able to return 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
+4
source share
5 answers

, Ruby-way, Enumerable , , .

, , :

def three_greatest(list)
  list.sort.reverse.first(3)
end

, , , . , . , .

, Enumerable, , max:

def three_greatest(list)
  list.max(3)
end

, Enumerable, -, . , , , , , .

, , . , , .

+11

max, sort :

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

:

ary = (1..1_000).to_a.shuffle

:

# >> 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

:

ary = (1..10_000).to_a.shuffle

:

# >> 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

, max (3) , .

:

a.max(2) #=> ["horse", "dog"]

, , :

ary.max(3) # => [100, 99, 98]

Benchmark :

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)

:

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)

:

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)
+6

greatest_number

  nums.delete(greatest_number)
  three_greatest_idx += 1
  greatest_number = nil # this line
end

, Ruby , , .

+3

, , Enumerable . . . : N :

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
+2

Ruby .

[8, 1, 10, 4].sort[-3]
>> 4

Edit: after many tests, I determined that the sorting method shown above is faster than the method below if, when searching for the nth largest number in an array of m elements, n> 1/20 is size m. Since in your example we are looking for 3rd place in an array of 4 elements, and 3 is much larger .2, the answer above is much more efficient than this alternative method:

[8, 1, 10, 4].max(3)[-1]
>> 4
+1
source

Source: https://habr.com/ru/post/1667903/

More articles:


All Articles