题目描述(中等难度)

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

关键就是刚好是什么意思?比如说原数字是 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 提供的动图更好理解一些。

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

再看下代码吧。

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,理了下思路。

results matching ""

    No results matching ""