[LeetCode] 31. Next Permutation 下一个排列

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 31. Next Permutation 下一个排列,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

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

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

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

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

给定一个排列,求下一个排列顺序,按照词典顺序,若是是最后一个排列就返回第一个排列。要求in-place和常量内存。code

当一个序列为非递减序列时,它必然是该组数的最小的排列数;同理,当一个序列为非递增序列时,它必然是该组数的最大的排列数。htm

解法:从低位向高位(从右向左)找第一个递减的数:nums[i]<nums[i+1],找出后面的最长的非递增子序列。若是不存在,则代表该permutation已经最大,next permutation为当前序列的逆序。好比nums[i]<nums[i+1],则nums[i+1]...nums[n]均知足前一个元素大于等于后一个元素,即这个子序列非递增。把nums[i+1]...nums[n]中比nums[i]大的数中最小的一个与nums[i]交换,而后把nums[i+1]...nums[n]逆序。blog

Java:排序

public void nextPermutation(int[] num) {
    int n=num.length;
    if(n<2)
        return;
    int index=n-1;        
    while(index>0){
        if(num[index-1]<num[index])
            break;
        index--;
    }
    if(index==0){
        reverseSort(num,0,n-1);
        return;
    }
    else{
        int val=num[index-1];
        int j=n-1;
        while(j>=index){
            if(num[j]>val)
                break;
            j--;
        }
        swap(num,j,index-1);
        reverseSort(num,index,n-1);
        return;
    }
}

public void swap(int[] num, int i, int j){
    int temp=0;
    temp=num[i];
    num[i]=num[j];
    num[j]=temp;
}

public void reverseSort(int[] num, int start, int end){   
    if(start>end)
        return;
    for(int i=start;i<=(end+start)/2;i++)
        swap(num,i,start+end-i);
}  

Python:内存

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # find longest non-increasing suffix
        right = len(nums)-1
        while nums[right] <= nums[right-1] and right-1 >=0:
            right -= 1
        if right == 0:
            return self.reverse(nums,0,len(nums)-1)
        # find pivot
        pivot = right-1
        successor = 0
        # find rightmost succesor
        for i in range(len(nums)-1,pivot,-1):
            if nums[i] > nums[pivot]:
                successor = i
                break
        # swap pivot and successor
        nums[pivot],nums[successor] = nums[successor],nums[pivot]  
        # reverse suffix
        self.reverse(nums,pivot+1,len(nums)-1)
        
    def reverse(self,nums,l,r):
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l += 1
            r -= 1 

Python:

class Solution:
    def nextPermutation(self, num):
        k, l = -1, 0
        for i in xrange(len(num) - 1):
            if num[i] < num[i + 1]:
                k = i
                
        if k == -1:
            num.reverse()
            return
        
        for i in xrange(k + 1, len(num)):
            if num[i] > num[k]:
                l = i
                
        num[k], num[l] = num[l], num[k]
        num[k + 1:] = num[:k:-1]

C++:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int i, j, n = num.size();
        for (i = n - 2; i >= 0; --i) {
            if (num[i + 1] > num[i]) {
                for (j = n - 1; j > i; --j) {
                    if (num[j] > num[i]) break;
                }
                swap(num[i], num[j]);
                reverse(num.begin() + i + 1, num.end());
                return;
            }
        }
        reverse(num.begin(), num.end());
    }
};

C++:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()<2) return;
        int n = num.size(), j = n-2;
        while(j>=0 && num[j]>=num[j+1]) j--;
        
        if(j<0) {
            sort(num.begin(),num.end());
            return;
        } 
        
        int i=j+1;
        while(i<n && num[i]>num[j]) i++;
        i--;
        
        swap(num[i],num[j]);
        sort(num.begin()+j+1, num.end());
    }
};

  

相似题目:

[LeetCode] 46. Permutations 全排列

[LeetCode] 47. Permutations II 全排列 II 

[LeetCode] 60. Permutation Sequence 序列排序

 

All LeetCode Questions List 题目汇总