lintcode:next permutation下一个排列

时间:2022-09-10 11:35:08

题目

下一个排列

给定一个整数数组来表示排列,找出其之后的一个排列。

样例

给出排列[1,3,2,3],其下一个排列是[1,3,3,2]

给出排列[4,3,2,1],其下一个排列是[1,2,3,4]

注意

排列中可能包含重复的整数

解题

和上一题求上一个排列应该很类似

1.对这个数,先从右到左找到递增序列的前一个位置,peakInd

2.若peakInd = -1 这个数直接逆序就是答案了

3.peakInd>= 0 peakInd这个位置的所,和 peakInd 到nums.size() -1 内的数比较,返回 nums[peakInd] < nums[swapInd]最大的下标 swapInd

nums[swapInd] 是和nums[peakInd] 最接近并且比 nums[peakInd]大的数,这两个数进行交换

4.同样,peakInd + 1 到nums.length() - 1 内的数进行逆序

Python

class Solution:
# @param num : a list of integer
# @return : a list of integer
def nextPermutation(self, nums):
# write your code here
peakInd = len(nums) - 1
while peakInd>0 and nums[peakInd] <= nums[peakInd-1]:
peakInd -=1
peakInd -=1
if peakInd>=0:
swapInd = peakInd + 1
while swapInd< len(nums) and nums[swapInd]> nums[peakInd]:
swapInd +=1
swapInd -=1
nums[swapInd],nums[peakInd] = nums[peakInd],nums[swapInd]
left = peakInd + 1
right = len(nums) - 1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left +=1
right -=1
return nums

Python Code

Java

public class Solution {
/**
* @param nums: an array of integers
* @return: return nothing (void), do not return anything, modify nums in-place instead
*/
public int[] nextPermutation(int[] nums) {
// write your code here
int peakInd = nums.length-1;
while(peakInd>0 && nums[peakInd-1] >= nums[peakInd]){
peakInd --;
}
peakInd --;
if(peakInd>=0){
int swapInd = peakInd + 1;
while(swapInd< nums.length && nums[swapInd] > nums[peakInd]){
swapInd ++;
}
swapInd --;
swapnums(nums,peakInd,swapInd);
}
int left = peakInd + 1;
int right = nums.length - 1;
while(left< right){
swapnums(nums,left,right);
left +=1;
right -=1;
} return nums;
}
private void swapnums(int[] nums,int left,int right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}

Java Code