力扣经典题目解析--下一个排列(字节面试题)

这是一道中等难度的字节秋招面试题，很多伙伴都被问到了，同时也有很多同学表示连题目都看不懂，我们来看下原题

原题

题目地址: . - 力扣（LeetCode）

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

例如，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,2,3]我们可以看成是整数123,这三个数字可以组成6个整数123,132,213,231,312,321,这6个整数从小到大排列，123的下一个排列就是132,如果给定的数组是[3,2,1]没有比他更大的数字了，就取最小数123,当然这种是方便理解的描述，实际情况要复杂点，因为数组里面的元素是整数，所以可能是10,100等,你无法通过拼接成整数去比较

暴力法

通过排列组合找出所有的数组排列方式，然后排序，找出下一个排列，时间复杂度是n!,我们来看下时间复杂度排名 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn),n的阶乘排在倒数第二位，时间复杂度比n的指数还要高，跑测试用例的时候会直接无响应，所以pass

一遍扫描

我们来看组数字,[1,3,8,7,6,2],这组数字最大数是[8,7,6,3,2,1]。看出啥规律没？没错，最大数是降序排列的，除去这个最大数，我们必然能找到这个数组里面有升序排列的数，比如1,3,8都是升序排列的，我们只要把升序排列的换下位置，就能找到比这个大的数，比如1和3换下位置就是[3,1,8,7,6,2],比原数组大，但是这个只是满足了条件一，还有一个条件是比原数组大比其他小如何满足？我们知道越往左权重越大，所以我们要从右往左找，找到一个升序数字3和8,那直接调换3和8行不行？还是不行，要从3开始取出到右边的所有数也就是3,8,7,6,2找到比3大比其他小的数也就是6，然后剩下的数升序排列就行了，结果是[1,6,2,3,7,8]

代码实现:

public void nextPermutation(int[] nums) {
    int n = nums.length;
    // 1. 从后往前找到升序子序列，找到第一次下降的数，位置记为k
    int k = n - 2;
    while (k >= 0 && nums[k] >= nums[k + 1]) {
        k--;
    }
    // 2. 如果k为-1，说明所有数为降序排列,是最大数,改成升序排列
    if (k == -1) {
        Arrays.sort(nums);
        return;
    }
    // 3. 依次遍历剩余降序排列的部分，找到要替换的最高位数
    int i = k + 1;
    while (i < n && nums[i] > nums[k]) {
        i++;
    }
    // 调换k和i-1位置的数
    int temp = nums[k];
    nums[k] = nums[i - 1];
    nums[i - 1] = temp;
    // 4.将k后的数升序排列,由于k后的数都是降序排列的，直接调换位置就行了
    int start = k + 1, end = nums.length - 1;
    while (start < end) {
        int reTemp = nums[start];
        nums[start] = nums[end];
        nums[end] = reTemp;
        start++;
        end--;
    }
}

效果: