你的位置:首页 > Java教程

[Java教程]Lintcode: Previous Permuation


Given a list of integers, which denote a permutation.Find the previous permutation in ascending order.NoteThe list may contains duplicate integers.ExampleFor [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]

跟Next Permutation很像,只不过条件改成

for (int i=nums.lenth-2; i>=0; i--)

  if (nums[i] > nums[i+1]) break;

for (int j=i; j<num.length-1; j++) 

  if (nums[j+1]>=nums[i]) break;

 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     // write your code 8     if (nums==null || nums.size()==0) return nums; 9     int i = nums.size()-2;10     for (; i>=0; i--) {11       if (nums.get(i) > nums.get(i+1)) break;12     }13     if (i >= 0) {14       int j=i;15       for (; j<=nums.size()-2; j++) {16         if (nums.get(j+1) >= nums.get(i)) break;17       }18       int temp = nums.get(j);19       nums.set(j, nums.get(i));20       nums.set(i, temp);21     }22     reverse(nums, i+1);23     return nums;24   }25   26   public void reverse(ArrayList<Integer> nums, int k) {27     int l = k, r = nums.size()-1;28     while (l < r) {29       int temp = nums.get(l);30       nums.set(l, nums.get(r));31       nums.set(r, temp);32       l++;33       r--;34     }35   }36 }