使该红宝石算法更快

Question

给定正整数n，我希望找到由m中包含的不超过n的数字组成的最大整数n。

除非返回以下结果之一，否则代码将返回m，在这种情况下，应返回-1。

• 没有可能的变化；
• 如果位数不等于输入的数字；
• 如果输出的第一位== 0;

我的代码有效，但是当“ n”是一个很大的数字时，它花费的时间太长！我相信是由于#Permutation方法造成的，但我不确定。谁能阐明这一点？这是我的代码

def next_smaller (n)
  new = n.to_s.split("").permutation.to_a.map { |n| n.join.to_i }
  res = new.sort.reverse.select { |x| x < n }.first
  res_arr = res.to_s.split("")
  res.nil? || res_arr.count != n.to_s.split("").count || res_arr[0] == 0 ? -1 : res
end

谢谢

Answer 1

以下内容应该相对有效。

def largest(n)
  nbr_chars = n.to_s.size
  n.digits.
    permutation(3).
    map { |a| a.join.to_i }.
    reject { |m| m.to_s.size < nbr_chars }.
    sort_by { |m| -m }.
    find { |m| m < n }
end

largest(907) #=> 790
largest(531) #=> 513
largest(135) #=> nil
largest(106) #=> nil

我建议返回nil而不是返回-1，前提是（如135一样）不存在产生小于给定整数的整数的重排。但是，如果在这种情况下需要-1，则将最后一行更改为

find { |m| m < n } || -1

注意：

790.digits #=> [0, 9, 7]

请参见Integer#digits。另请参见Array#permutation和Enumerable#max_by。