LeetCode Hot100 31.下一个排列

2023-12-25 08:44:30

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]
示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]
示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

提示:
1 <= nums.length <= 100
0 <= nums[i] <= 100

题目解法

本题实质上使用的解法应当是双指针+贪心算法的应用。

本题的重点在于位置带来的权重与数字大小带来的权值之间的平衡。

要获得下一个最大排列,最简单的想法就是把前面的“小数”与后面的“大数”相交换。同时小数越靠右越好,大数越小越好
这是因为小数越靠右权重就越小,所以这个位置换上大数后影响也就越小。
大数越小,造成的影响也就越小。

有了这个思想,我们令大数指针为 i ,小数指针为 j。大数指针从右向左寻找,这是因为为了让大数尽量靠近右边。

当局部出现从左向右递减数列时,我们必须跳过
这是因为局部此时已经是最大情况了,想要更大不可能。只能跳过。

所以得到大数指针如下:

int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

但是如果整个数组都是递减数组,那么 i 的值将会是-1。这种情况直接翻转整个数组即可。因此在此处用 if 划分出不同的情况。

当 i >= 0时,就说明此时的地址指针有效。我们再去寻找小数指针 j 。
小数指针同样从右向左寻找。一是因为右边位置权值小,二是因为右边的大数指针刚刚经历过递减数列,找到小数的循环次数少。

if (i >= 0) {
            int j = 0;
            while (j < nums.length && nums[i] >= nums[j]) {
                j++;
            }
            swap(nums, i, j);
        }

找到之后交换大数和小数的位置。
然后反向原大数指针位置后一位置的所有数列。这是因为后面跳过的都是递减数列,reverse之后变成了递增数列,整体变小。

完整代码

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--;
        }
    }
}

文章来源:https://blog.csdn.net/SpaceTravellers/article/details/135168846
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。