Leetcode日记— 31. Next Permutation

发布于 2020-11-10  111 次阅读


题目如下:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

思路:

本题就是找出在数组中所有数字的排列组合中比当前数字组合大的最小数字,若已经为最大数字则循环至把数组变为排列组合中的最小数字。

我们可以想到,应该从低位向高位寻找,找到第一个使得已遍历到的序列不为升序的数字,并让其与右边大于他的最小数字与其交换。因为若为升序序列,则与地位的任意数字交换都不能使当前数变大。同时,与比其大的最小数字交换才能得到比当前数字组合大的最小数字。

可以预见到,交换后右边依然是一个递增序列,那么在这个序列内左右倒置(也就是把越大的数字放在越低的位),就可以得到比当前数字组合大的最小数字。

在这里,需要注意的是:若遍历至nums[0]都依然为升序序列则说明当前已经是所有数字排列组合中最大的了,那么我们可以直接前后倒置,得到最小排列组合。

代码如下

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

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

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


你好哇!欢迎来到雷公马碎碎念的地方:)