leetcode31-下一个排列

蓝星 2020年01月04日 260次浏览

对于第31题,“寻找下一个排列”,虽说是一个media的题,但想要很快找到规律还是有一定的困难的。因此记录下来解题的过程,方便后续复习使用。

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路

解这道题着实废了一点时间,主要是被题目给的示例把思路带偏了。看到示例后,首先想到从右向左遍历数组,找到第一个比当前定位(index)的数小的位置,交换对应的数据即可获得下一个最大的排列。但是按照这个思路,示例可以满足,但卡在(1,3,2)这个用例上。按照上述思路得到的结果是(2,3,1),实际期望的值应该是(2,1,3)。所以上述思路不正确,需要考虑其他解法。

我们再以(8,5,1,4,3,2,1)作为示例,其下一个最大的排列是(8,5,2,1,1,3,4)。我们可以分以下几个步骤解决这个问题

  1. 从右向左遍历数组,获取数组的第一个极大值(4)
  2. 确定极大值后,可以将数组分为左右两个部分,对于左半部分,其最后一位i(极大值左边第一位)对应的值肯定小于右半部分(包括极大值在内)的某个值,只需要将该值和右半部分第一个大于该值(j)的数据进行交换即可
  3. 交换后,右半部分按照升序排序即可获的最终结果

代码

class Solution {

    /**
     * 从数组的最右侧开始,向左遍历,先找到第一个极大值(mid)
     * 将极值左边的第一个数和右边的比该数大的第一个数进行交换
     * 将极值及其右边的数按从小到大进行排序,即可获得下一个排列
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int index = nums.length - 1;
        //获取极大值
        while (index > 0){
            if (nums[index] > nums[index - 1]){
                break;
            }
            --index;
        }
        if (index == 0){
            Arrays.sort(nums);
            return;
        }

        //极大值左边第一个数
        int leftMinValue = nums[index - 1];

        for (int i = nums.length - 1; i >= index; --i){
            //和右边的第一个大于leftMinValue的位置进行交换
            if (nums[i] > leftMinValue){
                swap(nums, i, index - 1);
                break;
            }
        }
        //对index后边的进行排序,将其转变为最小的排列
        Arrays.sort(nums, index, nums.length);

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

总结

“获取极值”是算法中比较常用的一种思路,特别是对于数组一类的题目,后续可能还会遇到需要通过“极值”来解决的题目。