From c658e88544fa3bb87beb620f23f1bcb1437ed04a Mon Sep 17 00:00:00 2001 From: mo Date: Sun, 20 Aug 2017 22:37:51 -0600 Subject: study bcc32 solution. --- .../kth_largest_element_spec.rb | 23 ++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/spec/heaps_stacks_queues/kth_largest_element_spec.rb b/spec/heaps_stacks_queues/kth_largest_element_spec.rb index 5bbc0b4..49c0b70 100644 --- a/spec/heaps_stacks_queues/kth_largest_element_spec.rb +++ b/spec/heaps_stacks_queues/kth_largest_element_spec.rb @@ -29,6 +29,29 @@ describe "#kth_largest_element" do numbers.sort[-k] end + #def kth_largest_element(numbers, k) + #items = Array.new(105) + #numbers.each do |n| + #items[n] = n + #end + #items.compact[-k] + #end + + def kth_largest_element(numbers, k) + return numbers[0] if numbers.size == 1 + + numbers.shuffle! + partition = numbers[0] + upper = numbers[1..-1].find_all { |x| x >= partition } + + if upper.size >= k + kth_largest_element(upper, k) + else + lower = numbers[1..-1].find_all { |x| x < partition } + [partition] + kth_largest_element(lower, k - upper.size) + end + end + [ { nums: [7, 6, 5, 4, 3, 2, 1], k: 2, x: 6 }, { nums: [99, 99], k: 1, x: 99 }, -- cgit v1.2.3