题目
上一个排列
给定一个整数数组来表示排列,找出其上一个排列。
给出排列[1,3,2,3]
,其上一个排列是[1,2,3,3]
给出排列[1,2,3,4]
,其上一个排列是[4,3,2,1]
排列中可能包含重复的整数
解题
排列的特征
123 的排列依次是:123、132、213、231、312、321
要点:
1.整体来说是升序的
2.对一个数而言,各位数字中,大的数字越靠后,这个数在排列的位置越靠前,同样,小的数字越靠前,这个数在排列的位置越靠前
1.对每位数字,先找到从右到左递减序列的前一个位置
2.当这个位置是-1的时候,原数字逆序就是答案,比如是12345,右到左递减序列的前一个位置是 -1 ,原数字直接逆序:54321 就是答案,注意这里的排列要是和循环的,不然第一个数没有前一个数了
3.当这个位置不是-1 说明原数字不是排列中的第一个数
设这个位置是peakInd,这个位置的数是nums[peakInd] 。我们知道nums[peakInd] > nums[peakInd +1] 但是不是nums中从 peakInd 到nums.size() -1 内的数都一定小于nums[peakInd],我们找到第一个nums[swapInd] > nums[peakInd] 并将这两个数进行交换
4.交换之后从peakInd + 1 到nums.size() -1 这里的数也一定是非递减的,对这部分的数逆序后,整体的数就是答案了。
比如:40712389 右到左递减序列的前一个位置是peakInd = 2 ,3到7内左到右第一个大于7的数是8,其位置是6,交换这个两个位置的数后:40812379,下面在对3 到7位置内的数进行逆序后:40897321.就是答案了。
这里的第一点就是,先找到右到左的递减序列,这个递减序列“逆序”后,左到右就是递增的序列,上面递减序列数字组成的最大的数。
同时要对找到的递减序列前一个数,和该递减序列的第一个大于它的数进行交换,至于为什么,我不是很理解,最后逆序就是上一行刚说的了。
Java
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
// write your code
int peakInd = nums.size() - 1;
// 从后向前走,找到第一个nums[peakInd - 1] > nums[peakInd] 退出
// 后向前走 降序序列的最后一个位置跳出
while(peakInd > 0 && nums.get(peakInd - 1) <= nums.get(peakInd)){
peakInd--;
}
//降序序列的前一个位置
peakInd--;
if(peakInd >= 0){
int swapInd = peakInd + 1;
while(swapInd< nums.size()
&& nums.get(swapInd) < nums.get(peakInd)){
swapInd++;
}
swapInd--;
int tmp = nums.get(swapInd);
nums.set(swapInd,nums.get(peakInd));
nums.set(peakInd,tmp);
}
int left = peakInd + 1;
int right = nums.size() - 1;
while(left < right){
int tmp = nums.get(left);
nums.set(left,nums.get(right));
nums.set(right,tmp);
left ++;
right --;
}
return nums;
}
}
Java Code
凭借刚做的印象有写了一遍
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
// write your code
int peakInd = nums.size() - 1;
while(peakInd >0 && nums.get(peakInd)>=nums.get(peakInd-1)){
peakInd --;
}
peakInd --;
if(peakInd >=0){
int swapInd = peakInd + 1;
while(swapInd < nums.size() && nums.get(peakInd) >nums.get(swapInd)){
swapInd +=1;
}
swapInd--;
int tmp = nums.get(swapInd);
nums.set(swapInd,nums.get(peakInd));
nums.set(peakInd,tmp);
}
int left = peakInd + 1;
int right = nums.size() - 1;
while(left < right){
int tmp = nums.get(left);
nums.set(left,nums.get(right));
nums.set(right,tmp);
left++;
right--;
}
return nums;
}
}
Java Code
Python
class Solution:
# @param num : a list of integer
# @return : a list of integer
def previousPermuation(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[peakInd] > nums[swapInd]:
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