宁波科技网站建设,旧手机服务器wordpress,站长源码之家,江小白网络营销案例首先理解整数的字典序#xff0c;字典序排列总是优先让“较小的”元素出现在前面。字典序的排列规则类似于字典中的单词排列方式#xff0c;从左到右逐位比较#xff0c;较小的数字优先出现。按照正整数元素排列的字典序#xff0c;如果将每个排列视为一个整数值#xff0…
首先理解整数的字典序字典序排列总是优先让“较小的”元素出现在前面。字典序的排列规则类似于字典中的单词排列方式从左到右逐位比较较小的数字优先出现。按照正整数元素排列的字典序如果将每个排列视为一个整数值那么这些排列确实是以升序排列的。
例如对于数组 [1, 2, 3, 4]字典序排列如下
[1, 2, 3, 4] → 1234[1, 2, 4, 3] → 1243[1, 3, 2, 4] → 1324[1, 3, 4, 2] → 1342[1, 4, 2, 3] → 1423[1, 4, 3, 2] → 1432[2, 1, 3, 4] → 2134[2, 1, 4, 3] → 2143[2, 3, 1, 4] → 2314[2, 3, 4, 1] → 2341[2, 4, 1, 3] → 2413[2, 4, 3, 1] → 2431[3, 1, 2, 4] → 3124[3, 1, 4, 2] → 3142[3, 2, 1, 4] → 3214[3, 2, 4, 1] → 3241[3, 4, 1, 2] → 3412[3, 4, 2, 1] → 3421[4, 1, 2, 3] → 4123[4, 1, 3, 2] → 4132[4, 2, 1, 3] → 4213[4, 2, 3, 1] → 4231[4, 3, 1, 2] → 4312[4, 3, 2, 1] → 4321 如果只有一个元素下一个排列是其本身。
java 实现代码
class Solution {public void nextPermutation(int[] nums) {int n nums.length;if(n 2) return; //由于返回类型是void所以如果只有一个元素下一个排列是其本身。int i n - 2; // i 是从右往左第一个两个相邻元素中前面的元素小于后面的元素时前面这个元素的索引位置while(i 0 nums[i] nums[i 1]) {i--;}if(i 0) {//寻找比nums[i]大的最小元素int j n - 1;//此时i右端所有元素相当于是逆序递减排列//所以j从最右端开始遍历第一个比i大的元素就是比nums[i]大的最小元素while(nums[j] nums[i]) {j--;}//交换nums[j] 和 nums[i]swap(nums, i, j); // swap交换数组nums下标i和j上的元素}//如果是字典序最大的排序此时, i -1, i 1 0reverse(nums, i 1, n - 1); //理解从 i 1 开始}private void reverse(int[] nums, int start, int end) {while(start end) {swap(nums, start, end);start;end--;}}private void swap(int[] nums, int i, int j) { //交换数组下标i和j上的元素int temp;temp nums[i];nums[i] nums[j];nums[j] temp;}
}
