[LintCode] 51. Previous Permutation

xiaoxiao2021-02-28  7

public class Solution { /* * @param nums: A list of integers * @return: A list of integers that's previous permuation */ public List<Integer> previousPermuation(List<Integer> nums) { int cur = nums.size() - 1; for(;cur >=1;cur--){ //找拐点，如果前面一个数大于当前数，前面一个数是拐点， //在拐点后找一个最大的且比拐点小的数，和拐点交换 if(nums.get(cur - 1) > nums.get(cur)){ int start = cur; int max = nums.get(start); int index = start; for(;start<nums.size();start++){ if(nums.get(start) > max && nums.get(start) < nums.get(cur - 1)){ max = nums.get(start); index = start; } } int temp = nums.get(cur - 1); nums.set(cur - 1, nums.get(index)); nums.set(index, temp); //对拐点之后的数从大到小排列 sortArray(nums,cur); break; } } System.out.println(cur); if(cur <= 0){ sortArray(nums,0); } return nums; } //对数组从start位置开始大到小排列 void sortArray(List<Integer> nums,int start){ List<Integer> temp = new ArrayList<>(); for(int i=start;i<nums.size();i++){ temp.add(nums.get(i)); } Collections.sort(temp); int index = 0; for(int i=temp.size() - 1;i>=0;i--){ nums.set(start + index, temp.get(i)); index ++; } } }