ruby - 寻找下一个最大的整数

Question

我想从给定整数中的字符组成的整数中找到下一个最大的整数。如果给定的整数是最大的，则返回 -1。

def next_bigger(n)
  perm = n.to_s.chars.sort.permutation.to_a.uniq
  to_return = []
  perm.each do |x|
    to_return.push(x.join)
  end
  tracker = to_return.find_index(n.to_s)
  if to_return[tracker + 1] != nil
    return to_return[tracker + 1].to_i
  else
    -1
  end
end

此代码有效。我不知道如何让它更轻。现在需要永远运行。你会从哪里开始？

Answer 1

您可以使用递归来获得高效的过程。

代码

def next_largest(n)
  nxt = nl(n.to_s.chars.map(&:to_i))
  return nil if nxt.nil?
  nxt.map(&:to_s).join.to_i
end

def nl(arr, remaining_digits=arr.sort)
  if arr.size == 1
    return (remaining_digits.first > arr.first) ? remaining_digits : nil
  end 

  first = arr.first
  remaining_arr = arr.drop(1)

  remaining_digits.each_index do |i|
    d = remaining_digits[i]
    rest =
    case i
    when 0 then remaining_digits.drop(1)
    when remaining_digits.size-1 then remaining_digits[0..-2]
    else [*remaining_digits[0..i-1], *remaining_digits[i+1..-1]]
    end
    return [d, *rest] if d > first
    if d == first
      arr = nl(remaining_arr, rest)
      return [d, *arr] if arr
    end
  end
  nil    
end  

示例

(1..10000).to_a.sample(10).sort.each do |n|
  v = next_largest(n)
  print "%4d => " % n
  puts(v ? ("%4d" % v) : "No next number")
end
 647 =>  674
1137 => 1173
4010 => 4100
4357 => 4375
6542 => No next number
6832 => 8236
6943 => 9346
7030 => 7300
8384 => 8438
9125 => 9152

next_largest(613_492_385_167)
  #=> 613492385176

所有这些计算只用了不到一秒钟。

解释

(时间允许时提供...)