1. 題目

整數(shù)數(shù)組的一個(gè) 排列 就是將其所有成員以序列或線性順序排列。

• 例如，arr = [1,2,3] ，以下這些都可以視作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整數(shù)數(shù)組的 下一個(gè)排列 是指其整數(shù)的下一個(gè)字典序更大的排列。更正式地，如果數(shù)組的所有排列根據(jù)其字典順序從小到大排列在一個(gè)容器中，那么數(shù)組的 下一個(gè)排列 就是在這個(gè)有序容器中排在它后面的那個(gè)排列。如果不存在下一個(gè)更大的排列，那么這個(gè)數(shù)組必須重排為字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一個(gè)排列是 [1,3,2] 。
• 類似地，arr = [2,3,1] 的下一個(gè)排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一個(gè)排列是 [1,2,3] ，因?yàn)?[3,2,1] 不存在一個(gè)字典序更大的排列。

給你一個(gè)整數(shù)數(shù)組 nums ，找出 nums 的下一個(gè)排列。

必須 原地 修改，只允許使用額外常數(shù)空間。

2.分析

這里需要找下一個(gè)字典序更大的排列，那么意味著要從數(shù)組的后端入手。如果最后兩個(gè)元素原本就是升序的，那么就直接交換這兩個(gè)元素就好了，這個(gè)組合即使下一個(gè)更大的組合。
但是，如果這兩個(gè)元素不是升序的，那么交換這兩個(gè)元素反而導(dǎo)致拍列更小。因此，必須要找到從后向前數(shù)的第一個(gè)升序排列的兩個(gè)相鄰元素。找到之后，交換這兩個(gè)元素即可。

但是，交換后的元素依然不一定是下一個(gè)更大排列組合。如[5,7,6,4]這個(gè)排列，交換5和7，得到的是[7,5,6,4]這個(gè)組合，顯然不是下一個(gè)更大排列，畢竟手動(dòng)排列組合一下，發(fā)現(xiàn)下一個(gè)組合應(yīng)該是[6,4,5,7]

那么，應(yīng)該是考慮從后向前第一個(gè)升序段的后一個(gè)元素開(kāi)始，將后面所有的元素按字典排序，然后找到緊挨著升序點(diǎn)前一個(gè)元素的那個(gè)元素，將其交換即可。
或者找到緊挨著升序段前一個(gè)元素的數(shù)據(jù)，將其進(jìn)行交換，然后將從升序段后一個(gè)元素開(kāi)始的數(shù)據(jù)，按字典方式排序。

3.解答

3.1 先排序，后交換

public class Solution {public void nextPermutation(int[] nums) {if (nums.length <= 1) return;int len = nums.length;for (int i = len - 1; i > 0;i--) {if (nums[i] > nums[i - 1]) {Arrays.sort(nums, i, len);for (int j = i; j < len; j++) {if (nums[j] > nums[i - 1]) {int temp = nums[j];nums[j] = nums[i - 1];nums[i - 1] = temp;return;}}}}Arrays.sort(nums);}
}

3.2 先交換，后排序

public class Soultion {public void nextPermutation(int[] nums) {if (nums.length <= 1) return;int i = nums.length - 2;int j = nums.length - 1;int k = nums.length - 1;while (i >= 0 && nums[i] >= nums[j]) {i--;j--;} if (i >= 0) {while (nums[i] > num[k]) {k--;}swap(nums, i, k);}Arrays.sort(nums, j, nums.length);}private void swap(int[], int i, int k) {int temp = nums[i];nums[i] = nums[k];nums[k] = temp;}
}