资讯专栏INFORMATION COLUMN

LeetCode31.下一个排列 JavaScript

luxixing / 1998人阅读

摘要:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列即升序排列。

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

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

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

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

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

答案参考:

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    for(var i = nums.length - 1; i > 0 && nums[i] <= nums[i - 1]; i--);
    if(i === 0){
        reverse(0, nums.length - 1);
        return;
    }
    for(var j = i + 1; j < nums.length && nums[i - 1] < nums[j]; j++);
    swap(i - 1, j - 1);
    reverse(i, nums.length - 1);
    return;    
    
    function reverse(start, end){
        while(start < end){
            swap(start, end);
            start++;
            end--;
        }
    }
    function swap(i, j){
        var tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/101766.html

相关文章

  • leetcode 31 Next Permutation

    摘要:我们所找到的这个元素就是排序需要改变的第一个元素。然后我们选取一个刚好大于此元素的数,与当前元素进行替换。并对后面的所有元素重新按照升序排列就可以得到最终的答案。 题目详情 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of...

    binaryTree 评论0 收藏0
  • 力扣(LeetCode)31

    摘要:如果不存在下一个更大的排列,则将数字重新排列成最小的排列即升序排列。必须原地修改,只允许使用额外常数空间。 题目地址:https://leetcode-cn.com/probl... 题目描述:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空...

    forrest23 评论0 收藏0
  • leetcode31 Next Permutation

    摘要:如果当前数字代表的整数值已经是所有排列组合中的最大值,则返回当前数字组成的最小值。可是这意味着大量无用的数字的生成和比较。一个数字中的各个位上的数如何调整顺序才能获得一个最小的更大值。其次,要保证移动之后,高位以后的值为最小值。 题目要求 Implement next permutation, which rearranges numbers into the lexicographi...

    hedzr 评论0 收藏0
  • 6-9月技术文章汇总

    摘要:分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥?...

    miya 评论0 收藏0
  • LeetCode - 007 - 整数反转(reverse-integer)

    摘要:详细介绍将其他值转成数字值。此方法更改数组的长度。详细介绍解题思路首先,将传入的数字转换成字符串,并分割成数组。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-19 09:42:39 Recently revised in 2019-05-19 16:08:24 Hello 小伙伴们,如果觉得本文还不错,记得给个 star , 小伙伴们...

    venmos 评论0 收藏0

发表评论

0条评论

luxixing

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<