title: 算法小练——下一个排列
date: 2019-12-19 19:55:01
categories:

• Algorithms
  tags:
• medium

下一个排列

描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

示例

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

代码参考

class Solution {
   public void nextPermutation(int[] nums) {
        int i = nums.length -2;
        while (i>=0 && nums[i+1] <=nums[i]){ //从后往前循环判断整个数组，找到前一个数比后一个数大的 nums[i]
            i--;
        }
        if(i>=0){
            int j = nums.length - 1;
            while (j>=0 && nums[j] <= nums[i]){ //从后往前，找到比nums[i]大的第一个数
                j--;
            }
            swap(nums,i,j);//交换
        }
        reverse(nums,i+1);//对从i+1到最后的所有数从大到小排列
    }

private void reverse(int[] nums, int i) {
        int start = i, j = nums.length - 1;
        while (start < j) {
            swap(nums, start, j);
            start++;
            j--;
        }
    }

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

笔记

具体算法并不难写，主要要想清楚整个过程

首先是找到交换点，当前者比后者大时，则前者是交换点。

找到后者里比前者刚好大一点的那个进行交换，并且对

前者 后面的全部数字从小到大排列