1. 首页
  2. Leetcode经典148题

leetCode-31-Next-Permutation

题目描述(中等难度)

leetCode-31-Next-Permutation

这道题的的难度我觉得理解题意就占了一半。题目的意思是给定一个数,然后将这些数字的位置重新排列,得到一个刚好比原数字大的一种排列。如果没有比原数字大的,就升序输出。

关键就是刚好是什么意思?比如说原数字是 A,然后将原数字的每位重新排列产生了 B C D E,然后把这 5 个数字从小到大排列,比如是 D A B E C ,那么,我们要找的就是 B,就是那个刚好比 A 大的数字。

再比如 123,其他排列有 132,213,231,312,321,从小到大排列就是 123 132 213 231 312 321,那么我们要找的就是 132。

题目还要求空间复杂度必须是 O(1)。

#解法一

我们想几个问题。

要想使得数字变大,只要任意一位变大就可以。

要想得到刚好大于原来的数字,要变个位。

这里变大数字,只能利用交换。

如果从个位开始,从右往左进行,找一个比个位大的,交换过来,个位的数字交换到了更高位,由于个位的数字较小,所以交换过去虽然个位变大了,但数字整体变小了。例如 1 3 2,把 2 和 3 交换,变成 1 2 3,个位变大了,但整体数字变小了。

个位不行,我们再看十位,如果从十位左边找一个更大的数字交换过来,和个位的情况是一样的,数字会变小。例如 4 1 2 3,把 2 和 4 交换,2 1 4 3,数字会变小。如果从右边找一个更大的数字交换过来,由于是从低位交换过来的,所以数字满足了会变大。如 4 1 2 3,把 2 和 3 交换,变成 4 1 3 2 数字变大了。

如果十位右边没有比十位数字大的,我们就左移看下一位,再看当前位右边,有没有更大的数字,没有就一直左移就可以。

还有一个问题,如果右边有不止一个大于当前位的数字选哪个?选那个刚好大于当前位的,这样会保证数字整体尽可能的小。

交换完结束了吗?并没有。因为交换完数字变大了,但并不一定是刚好大于原数字的。例如 158476531,我们从十位开始,十位右边没有大于 3 的。再看百位,百位右边没有大于 5 的。直到 4 ,右边出现了很多大于 4 的,选那个刚好大于 4 的,也就是 5 。然后交换,变成 158576431,数字变大了,但并不是刚好大于 158476531,我们还需要将 5 右边的数字从小到大排列。变成158513467,就可以结束了。

而最后的排序,我们其实并不需要用排序函数,因为交换的位置也就是 5 的右边的数字一定是降序的,我们只需要倒序即可了。看一下 LeetCode 提供的动图更好理解一些。

leetCode-31-Next-Permutation

再看这个过程,我们其实是从右向左找到第一个数字不再递增的位置,然后从右边找到一个刚好大于当前位的数字即可。

再看下代码吧。

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    //找到第一个不再递增的位置
    while (i >= 0 && nums[i + 1] <= nums[i]) {
        i--;
    }
    //如果到了最左边,就直接倒置输出
    if (i < 0) {
        reverse(nums, 0);
        return;
    }
    //找到刚好大于 nums[i]的位置
    int j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
        j--;
    }
    //交换
    swap(nums, i, j);
    //利用倒置进行排序
    reverse(nums, i + 1);

}

private void swap(int[] nums, int i, int j) {
    int temp = nums[j];
    nums[j] = nums[i];
    nums[i] = temp;
}

private void reverse(int[] nums, int start) {
    int i = start, j = nums.length - 1;
    while (i < j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}

时间复杂度:最坏的情况就是遍历完所有位,O(n),倒置也是 O(n),所以总体依旧是 O(n)。

空间复杂度:O(1)。

开始看题的时候一直没理解,后来理解了题试了几种也没想出来,然后看了 Solution,理了下思路。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-31-Next-Permutation

链接:https://www.javajike.com/article/3168.html

« leetCode-30-Substring-with-Concatenation-of-All-Words
leetCode-32-Longest-Valid-Parentheses»

相关推荐

QR code