首页 > 代码库 > Leetcode31--->Next Permutation(数字的下一个排列)

Leetcode31--->Next Permutation(数字的下一个排列)

2024-08-14 08:42:44   218人阅读

题目： 给定一个整数，存放在数组中，求出该整数的下一个排列（字典顺序）；要求原地置换，且不能分配额外的内存

举例：

1,2,3 → 1,3,2；  
3,2,1 → 1,2,3；  
1,1,5 → 1,5,1；  

解题思路：

1.　由于要找出整数的下一个排列，且按照字典顺序，因此要找出当前排列中需要交换的的那个位，即找到从右到左第一个不满足升序的元素的前一个元素nums[index1], 以及从右到左第一个大于nums[index1]的元素nums[index2];

2.　交换两个元素；因为是按字典顺序排列的，而nums[index2]是第一个大于nums[index1]的元素，此时[index1 + 1, index2]之间的元素都是大于nums[index2]以及nums[index1]的，而nums[index2]是从右往左第一个大于nums[index1]的元素，因此[index2 + 1, len]的元素都是小于nums[index1]，因此当nums[index1]与nums[index2]交换后，[index1 + 1, len]之间的元素就是一个降序

3.　但是由于在交换了nums[index1]和nums[index2]元素后，nums[index2]元素后面本应该是按字典顺序最小的数字组合，而[index1 + 1,结尾]之间的元素是降序的，是字典顺序的最大组合排列，因此需要将[index1 + 1, 结尾]之间的数据全部逆转，才能得到字典的下一个排列组合；

代码如下：

 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 =http://www.mamicode.com/ nums[len]; 7         int index1 = -1; 8         int index2 = 0; 9         for(int i = len - 1; i >= 0; i--) // 找到从右往左第一个不满足升序的元素的前一个元素10         {11             if(data <= nums[i])12                 data =http://www.mamicode.com/ nums[i];13             else14             {15                 index1 = i;16                 break;17             }18         }19         if(index1 != -1) // 表示可以找到这样的数，即给定的数字不是降序20         {21             for(int i = len; i >=0; i--)  // 找到从右往左第一个大于第一次找到的那个元素的元素22             {23                 if(nums[i] > nums[index1])24                 {25                     index2 = i;26                     break;27                 }28             }29             exchange(nums, index1, index2);  //此时[index1 + 1, index2]之间的元素都是大于nums[index2]以及nums[index1]的，而nums[index2]是从右往左第一个大于nums[index1]的元素，因此[index2 + 1, len]的元素都是小于nums[index1],
　　　　　　　　　因此当nums[index1]与nums[index2]交换后，[index1 + 1, len]之间的元素就是一个降序
30         31         }32         index1 = index1 + 1;33         while(index1 < len)  // 将index1位置之后的元素全部逆转【index + 1, len】之间的元素是降序排列，而我们需要的是nums[index1]元素之后的最小排列组合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 =http://www.mamicode.com/ nums[index1];43         nums[index1] = nums[index2];44         nums[index2] = data;45     }46 }

 

Leetcode31--->Next Permutation(数字的下一个排列)


联系
我们