Ruby leetcode:Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Return the array [2, 1, 1, 0].
我的解法：
# @param {Integer[]} nums
# @return {Integer[]}
def count_smaller(nums)
len = nums.length
new_nums = Array[]
(0...len).each do |i|
#num = nums[i]
num = i +1
new_num = 0
(num...len).each do |j|
if nums[j] < nums[i] then
new_num += 1
else
next
end
end
new_nums.push(new_num)
end
new_nums
end
submission 结果：Submission Result: Time Limit Exceeded 感觉 ruby 完全没有入门。求大神们指点。
这看起来是 Java 风格的实现；Ruby 里面，算法也可有略微优雅的实现，献丑一下我的实现：
def count_smaller(nums)
nums.map.with_index {|_num, index| smaller_count_after(index, nums) }
end
def smaller_count_after(index, nums)
nums[index..-1].count {|num| num < nums[index] }
end
p count_smaller([5, 2, 6, 1])
正好翻到了这题 从提交的执行时间看 树状数组用的时稍微少了一点，其实和 merge sort 时间复杂度是一样的
def count_smaller(nums)
idxes = {}
nums.sort.each_with_index {|v, i| idxes[v] ||= i + 1}
i_nums = nums.map {|n| idxes[n] }
ft = FenwickTree.new(nums.size)
ans = Array.new(nums.size)
(0..(nums.size-1)).to_a.reverse.each do |i|
ans[i] = ft.sum(i_nums[i] - 1)
ft.add(i_nums[i], 1)
end
ans
end
class FenwickTree
attr_accessor :n, :sums
def initialize(n)
@n = n
@sums = Array.new(n + 1) { 0 }
end
def add(x, val)
while x <= n
sums[x] += val
x += lowbit(x)
end
end
def lowbit(x)
x & -x
end
def sum(x)
res = 0
while x > 0
res += sums[x]
x -= lowbit(x)
end
res
end
end