Ruby leetcode:Count of Smaller Numbers After Self

torubylist · 2015年12月14日 · 最后由 angelfan 回复于 2016年06月15日 · 2885 次阅读

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]) 

#1 楼 @qinfanpeng 这看起来才像 ruby,我写的真心看不下去。最近看元编程,看到代码块这章的时候,始终觉得无法透彻得理解。

上算法的时间复杂度一样,有更优解吗?

这个问题可以这样吗,在从右向左的过程中将已经遍历过的数组插入到一个二叉树中,左右的左节点就是比当前值小的所有数字

用 merge sort 或者 bst

1 楼的算法估计会超时,无法 AC

正好翻到了这题 从提交的执行时间看 树状数组用的时稍微少了一点,其实和 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
需要 登录 后方可回复, 如果你还没有账号请 注册新账号