Lintcode: Previous Permuation

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

Lintcode: PRevious PermuationGiven 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 }

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航