力扣(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;
        
    }
}

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

查看所有标签

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

计算机科学概论(第12版)

计算机科学概论(第12版)

[美] J.Glenn Brookshear、[美] Dennis Brylow / 刘艺、吴英、毛倩倩 / 人民邮电出版社 / 2017-1 / 69.00

《计算机科学概论》是计算机科学概论课程的经典教材,全书对计算机科学做了百科全书式的精彩阐述,充分展现了计算机科学的历史背景、发展历程和新的技术趋势。《计算机科学概论》首先介绍的是信息编码及计算机体系结构的基本原理,进而讲述操作系统和组网及因特网,接着探讨算法、程序设计语言及软件工程,然后讨论数据抽象和数据库方面的问题,讲述图形学的一些主要应用以及人工智能,以计算理论的介绍结束全书。《计算机科学概论......一起来看看 《计算机科学概论(第12版)》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具