实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
need_sort = true
(0..nums.length - 1).reverse_each do |i|
if nums[i - 1] && nums[i] > nums[i - 1]
ex_num = nums[i..-1].sort.find {|n| n > nums[i-1] }
ex_index = nums.index.with_index {|n, j| j > i - 1 && n == ex_num}
nums[i-1], nums[ex_index] = nums[ex_index], nums[i-1]
nums[i..-1] = nums[i..-1].sort
need_sort = false
break
end
end
nums.sort! if need_sort
end
注意@return {Void} Do not return anything, modify nums in-place instead.
,不要在里面新建数组,并且只能修改原nums,否则提交都会报错