首页 > 代码库 > LintCode-Previous Permuation
LintCode-Previous Permuation
Given a list of integers, which denote a permutation.
Find the previous permutation in ascending order.
Note
The list may contains duplicate integers.
Example
For [1,3,2,3], the previous permutation is [1,2,3,3]
For [1,2,3,4], the previous permutation is [4,3,2,1]
Analysis:
Find out the fisrt local minimum and add it and its later elements into a list from back to front. Add the element just before this minimum into list also, set the element as bar ( we will decrease it to some smaller value). Sort the list, find out the next value smaller than the bar, put it on the position that one before the local minimum, then put all left elements in the list to the array in the decreasing order.
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @return: A list of integers that‘s previous permuation 5 */ 6 public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) { 7 int len = nums.size(); 8 if (len==0 || len ==1) return nums; 9 10 ArrayList<Integer> buff = new ArrayList<Integer>();11 buff.add(nums.get(len-1));12 int index = len-2;13 while (index>=0 && nums.get(index)<= nums.get(index+1)){14 buff.add(nums.get(index));15 index--;16 }17 18 if (index>=0){19 buff.add(nums.get(index));20 int bar = nums.get(index);21 Collections.sort(buff);22 int index2 = buff.size()-2;23 while (!(buff.get(index2)!=bar && buff.get(index2+1)==bar)) index2--;24 nums.set(index,buff.get(index2));25 buff.remove(index2);26 index++;27 for (int i=buff.size()-1;i>=0;i--){28 nums.set(index,buff.get(i));29 index++;30 }31 return nums;32 } else {33 Collections.sort(buff, Collections.reverseOrder());34 return buff;35 } 36 }37 }
LintCode-Previous Permuation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。