Leetcode31--->Next Permutation(数字的下一个排列)
题目： 给定一个整数，存放在数组中，求出该整数的下一个排列（字典顺序）；要求原地置换，且不能分配额外的内存举例：
1,2,3 → 1,3,2；
3,2,1 → 1,2,3；
1,1,5 → 1,5,1；
解题思路：
1. 由于要找出整数的下一个排列，且按照字典顺序，因此要找出当前排列中需要交换的的那个位，即找到从右到左第一个不满足升序的元素的前一个元素nums, 以及从右到左第一个大于nums的元素nums;
2. 交换两个元素；因为是按字典顺序排列的，而nums是第一个大于nums的元素，此时之间的元素都是大于nums以及nums的，而nums是从右往左第一个大于nums的元素，因此的元素都是小于nums，因此当nums与nums交换后，之间的元素就是一个降序
3. 但是由于在交换了nums和nums元素后，nums元素后面本应该是按字典顺序最小的数字组合，而之间的元素是降序的，是字典顺序的最大组合排列，因此需要将之间的数据全部逆转，才能得到字典的下一个排列组合；
代码如下：
1 public class Solution {
2 public void nextPermutation(int[] nums) {
3 if(nums == null || nums.length < 1)
4 return;
5 int len = nums.length - 1;
6 int data = nums;
7 int index1 = -1;
8 int index2 = 0;
9 for(int i = len - 1; i >= 0; i--) // 找到从右往左第一个不满足升序的元素的前一个元素
10 {
11 if(data <= nums)
12 data = nums;
13 else
14 {
15 index1 = i;
16 break;
17 }
18 }
19 if(index1 != -1) // 表示可以找到这样的数，即给定的数字不是降序
20 {
21 for(int i = len; i >=0; i--)// 找到从右往左第一个大于第一次找到的那个元素的元素
22 {
23 if(nums > nums)
24 {
25 index2 = i;
26 break;
27 }
28 }
29 exchange(nums, index1, index2);//此时之间的元素都是大于nums以及nums的，而nums是从右往左第一个大于nums的元素，因此的元素都是小于nums,
因此当nums与nums交换后，之间的元素就是一个降序
30
31 }
32 index1 = index1 + 1;
33 while(index1 < len)// 将index1位置之后的元素全部逆转【index + 1, len】之间的元素是降序排列，而我们需要的是nums元素之后的最小排列组合
34 {
35 exchange(nums, index1, len);
36 index1 ++;
37 len --;
38 }
39 }
40 public void exchange(int[] nums, int index1, int index2)
41 {
42 int data = nums;
43 nums = nums;
44 nums = data;
45 }
46 }
页:
[1]