专栏首页算法半岛LeetCode-31 下一个排列

LeetCode-31 下一个排列

> 题目:31. 下一个排列

> 难度:中等

> 分类:数组

> 解决方案:数组遍历

今天我们学习第31题下一个排列,这是一个中等的数组题。我们先看看这道题的题目描述。

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。 必须原地修改,只允许使用额外常数空间。

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

1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1

分析

这是一个数组排列的题,首先我们需要弄明白什么是数组的下一个排列。我们可以对数字1、2和3这三个数形成的数组进行排列,如下图所示:

对具体排列方法分析如下图所示:

上述分析所对应的 java代码如下所示:

class Solution {    public void nextPermutation(int[] nums) {        // 从右向左遍历,存储第一个下降的数的坐标        int i = 0;        // 从右向左遍历,存储第一个大于nums[i]的数的坐标        int j = 0;
        if(nums == null || nums.length < 2)            return ;
        // 从右向左找到第一个降序的数,坐标为i        for(int k=nums.length -2; k>=0; k--){            if(nums[k] < nums[k+1]){                i = k;                break;            }        }
        // 从右向左找到第一个大于nums[i]的数,坐标为j        for(int k=nums.length-1; k>=0; k--){            if(nums[k] > nums[i]){                j = k;                break;            }        }
        // 交换 nums[i] 和 nums[j]        swap(nums, i, j);
        // 转置从i+1(0)到nums.length-1的数         int n = 0;        if(i == 0 && j == 0)            n = 0;        else             n = i + 1;        int m = nums.length-1;        while(n < m){            swap(nums, n, m);            ++n;            --m;        }    }
    // 数组中两个数字交换函数    private void swap(int[] nums, int i, int j){        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }}

Github地址

LeetCode-31 下一个排列:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A28_ImplementstrStr.java

参考链接

下一个排列:https://leetcode-cn.com/problems/next-permutation/

本文分享自微信公众号 - 算法半岛(jacob2359),作者:算法半岛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-18 四数之和

    今天我们学习第18题四数之和,这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题的...

    用户3470542
  • LeetCode-15 三数之和

    今天我们学习第15题三数之和,这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题...

    用户3470542
  • LeetCode-1 两数之和

    给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那 两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个...

    用户3470542
  • LeetCode 448. 找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    Michael阿明
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • LeetCode 18. 4Sum

    ShenduCC
  • LintCode 恢复旋转排序数组题目分析代码

    说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,...

    desperate633
  • LeetCode153|删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    码农王同学
  • LeetCode 80. 删除排序数组中的重复项 II

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

    Michael阿明
  • leecode刷题(3)-- 旋转数组

    所以我们按照字面意思,来改变数组下标,每次让最后一位数值和前一位数值交换,然后再将最后一位数值赋值为第一位数值,让数组排序。

    希希里之海

扫码关注云+社区

领取腾讯云代金券