optimize this ruby code
So this code will count the total number of pairs of numbers whose difference is K. it is naive method and I need to optimize it. suggestions?
test = $stdin.readlines
input = test[0].s开发者_运维技巧plit(" ")
numbers = test[1].split(" ")
N = input[0]
K = input[1]
count = 0
for i in numbers
current = i.to_i
numbers.shift
for j in numbers
difference = (j.to_i - current).abs
if (difference == K)
count += 1
end
end
end
puts count
Would have been nice for you to give some examples of input and output, but I think this is correct.
require 'set'
def count_diff(numbers, difference)
set = Set.new numbers
set.inject 0 do |count, num|
set.include?(num+difference) ? count+1 : count
end
end
difference = gets.split[1].to_i
numbers = gets.split.map { |num| num.to_i }
puts count_diff(numbers, difference)
Untested, hopefully actual Ruby code
Documentation for Set: http://www.ruby-doc.org/stdlib/libdoc/set/rdoc/classes/Set.html
require 'set'
numbers_set = Set.new
npairs = 0
numbers.each do |number|
if numbers_set.include?(number + K)
npairs += 1
end
if numbers_set.include?(number - K)
npairs += 1
end
numbers_set.add(number)
end
Someone deleted his post, or his post was deleted... He had the best solution, here it is :
test = $stdin.readlines
input = test[0].split(" ")
numbers = test[1].split(" ")
K = input[1]
count = 0
numbers.combination(2){|couple| couple.inject(:-).abs == K ? count++}
puts count
You don't even need N.
I do not know Ruby so I'll just give you the big idea:
- Get the list
- Keep a boolean array (call it
arr
), marking off numbers as true if the number exists in the list - Loop through the list and see if
arr[num-K]
and/orarr[num+K]
is true wherenum
is a number in your list
This uses up quite a bit of memory though so another method is to do the following:
- Keep a hash map from an integer
n
to an integercount
- Go through your list, adding
num+K
andnum-K
to the hash map, incrementingcount
accordingly - Go through your list and see if
num
is in the hash map. If it is, increment your counter bycount
精彩评论