Ruby 在力扣做的一道题,相当之诡异

ad583255925 · October 23, 2019 · Last by ad583255925 replied at October 29, 2019 · 5563 hits

https://leetcode-cn.com/problems/next-permutation/

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须原地修改,只允许使用额外常数空间。

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我的答案

# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
    result = nums.sort.dup
    (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]
            result = (nums[0..i-1] + nums[i..-1].sort).dup
            break
        end    
    end    
    result
end

我自己控制台跑 [1, 3, 2] 的时候,没问题,会返回[2, 1, 3],但是力扣永远给我输出[2,3,1],我在返回结果前的最后一行也打印了结果,确实是[2,1,3],不知道力扣用的哪个版本的 ruby,望各位帮忙也跑一下,看看结果,谢谢

next_permutation([1,3,2])

用你的代码试了一下,确实有你说的问题。力扣的 bug

在方法体开头加一行 nums = nums.dup 应该就好

Reply to luikore

这样空间复杂度 O(n) 了

# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
    result = nums.sort.dup # 这里符合题目要求的额外常数空间吗?
    (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]
            result = (nums[0..i-1] + nums[i..-1].sort).dup
            break
        end    
    end    
    result # 看注释,题目要求不返回值,只在 nums 上操作。为什么要返回 result 呢?
end
Reply to lithium4010

你的代码早就 O(n) * m 了

应该是你修改了传入的参数 nums 造成的问题

# @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
ad583255925 closed this topic. 29 Oct 09:39
You need to Sign in before reply, if you don't have an account, please Sign up first.