Next Permutation

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

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

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

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

[LeetCode] 31. Next Permutation 下一个排列 - Grandyang - 博客园

时间复杂度 o(n),space o(1)

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 0)
            return;
        
        //1 2^ 7 4 3 1
        //1 2  7 4 3& 1
        //1 3  7 4 2 1
        //1 3  1 2 4 7
        
        
        //1.当一个数组是从大到小排列时，那么他肯定是最大的排列
        //2. 从后往前找，比如上面的列子，从后往前找 1，3，4，7，2,从1-7一直是升序，也就是从前往后看是降序，
        //说明7 4 3 1这个partial array已经是最大排序了，下一个2小于他的下一个，所以对这个点来说还不是最大排序，
        //我们可以从后面找到一个和他绝对值最小的比他大的数来替换，从而可以实现找到下一个比他大的排序，
        //3. 仍旧从后往前找，因为2后面的数肯定是降序的，所以从后往前找的第一个大于2的数，就是我们要替换的数，
        //4,和2替换以后，因为之前2后面的数 都是降序，已经是最大排序了，所以我们只需要将他翻转就好了
        //从后往前找到第一个小于其后面的数的数 i,因为这个题是要找到比当前大的permutation,
        //从后往前找到的i，然后再次从后往前找，找到第一个大于i的数，两个交换，然后再把之前i后面的数进行翻转
        int firstSmall = -1;
        
        for(int i = nums.length -2; i >= 0; i--){
            if(nums[i] < nums[i+1]){
                firstSmall = i;
                break;
            }
        }
        
        //
        
        //当前已经是最大排序了，只需要翻转就可以
        if(firstSmall == -1){
            reverse(nums,0, nums.length-1);
            return;
        }
        
        
        int firstLarger = -1;
        
        for(int i = nums.length-1; i > firstSmall; i--){
            if(nums[i] > nums[firstSmall]){
                firstLarger = i;
                break;
            }
        }
        
        swap(nums,firstSmall, firstLarger);
        
        reverse(nums,firstSmall+1, nums.length-1);
        
        return;
        
    }
    
    public void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    public void reverse(int[] nums, int i, int j){
        while(i < j){
            swap(nums, i++,j--);
        }
    }
}