力扣(LeetCode)31

栏目: 编程工具 · 发布时间: 7年前

内容简介:题目描述:实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

题目描述:

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

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

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

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

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

解答:

直接给出步骤:

1从右到左扫描数组找出第一个升序对(nums[j-1],nums[j])

2从右到左扫描数组找出第一个大于nums[j-1]的数nums[k]

3交换nums[j-1],nums[k]

4对num[j...nums.length-1]转置。

java ac代码:

class Solution {
    public void nextPermutation(int[] nums) {
        boolean flag = true;
        int i = 0;
        for(;i < nums.length-1;i++)
            if(nums[i] < nums[i+1])
            {
                flag = false;
                break;
            }
        if(flag)
        {
            int x = 0,y = nums.length-1;
            while(x < y)
            {
                swap(nums,x,y);
                x++;
                y--;
            }
        }
        else
        {
            i = nums.length-1;
            while(i >= 1)
                if(nums[i] <= nums[i-1])i--;
            else break;
            int j = nums.length-1;
            for(;j >= 0;j--)
                if(nums[j] > nums[i-1])break;
            swap(nums,i-1,j);
            int x = i,y = nums.length-1;
            while(x < y)
            {
                swap(nums,x,y);
                x++;
                y--;
            }
        }
        
        
    }
    
    void swap(int[] nums,int x,int y)
    {
          int temp = nums[x];
          nums[x] = nums[y];
          nums[y] = temp;
        
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。

鸟哥的Linux私房菜

鸟哥的Linux私房菜

鸟哥 / 机械工业出版社 / 2008-1 / 88.00元

《鸟哥的Linux私房菜:服务器架设篇(第2版)》是对连续三年蝉联畅销书排行榜前10名的《Linux鸟哥私房菜一服务器架设篇》的升级版,新版本根据目前服务器与网络环境做了大幅度修订与改写。 全书共3部分,第1部分为架站前的进修专区,包括在架设服务器前必须具备的网络基础知识、Linux常用网络命令、Linux网络侦错步骤,以及服务器架站流程:第2部分为主机的简易防火措施,包括限制Linux对......一起来看看 《鸟哥的Linux私房菜》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具