首页 > 代码库 > LeetCode 31. Next Permutation (下一个排列)
LeetCode 31. Next Permutation (下一个排列)
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
题目标签:Array
Java Solution:
Runtime beats 85.79%
完成日期:07/13/2017
关键词:Array
关键点:找到需要被增大的那个数字A,再找到最接近于A且比A大的数字B,互换A和B,最后把B之后的所有数字sort
1 public class Solution 2 { 3 public void nextPermutation(int[] nums) 4 { 5 // from right to left, find the first number which is not in ascending order 6 for(int i=nums.length-1; i>=0; i--) 7 { 8 if(i == 0) // meaning all number are in ascending order 9 { 10 Arrays.sort(nums); 11 return; 12 } 13 else if(nums[i] > nums[i-1]) 14 { 15 // from right to left, find the first number is greater than nums[index_num] 16 for(int j=nums.length-1; j>=i-1; j--) 17 { 18 if(nums[j] > nums[i-1]) // swap them 19 { 20 int temp = nums[i-1]; 21 nums[i-1] = nums[j]; 22 nums[j] = temp; 23 // sort the rest numbers after i - 1 24 Arrays.sort(nums, i, nums.length);; 25 return; 26 } 27 } 28 } 29 } 30 } 31 32 33 }
参考资料:
http://www.cnblogs.com/grandyang/p/4428207.html
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 31. Next Permutation (下一个排列)