- n個元素有n!種排列方式显熏，你不會想都羅列出來再去找下一個排列吧
- 這種排序方式為字典序活喊，字典序就是將元素按字典的順序進(jìn)行排序
- 針對這個串生成全排列，就是依次生成"12345"→"12354"→"······"→"54321"
- 字典序法要求這一個與下一個排列有盡可能長的共同前綴，也即變化限制再盡可能短的后綴上霎肯，以<6,2,1,5,4,3,0>為例，<5,4,3,0>是最長降序序列（后綴）榛斯，直覺上應(yīng)該將1和3交換位置观游，以對前綴產(chǎn)生盡可能小的影響，現(xiàn)在我們的序列是<6,2,3,5,4,1,0>,<6,2,3>我們的前綴現(xiàn)在是最小的驮俗，這點(diǎn)毫無疑問懂缕，但后綴不一定是最小的。后綴交換前是降序的王凑，交換后也是降序的搪柑，所以現(xiàn)在只需要簡單翻轉(zhuǎn)即可聋丝。
public void nextPermutation(int[] nums) {
if (nums.length == 0 || nums == null) return;
int k = nums.length - 2;
while (k >= 0 && nums[k] >= nums[k + 1]) {
--k;
}
if (k == -1){
reverse(nums,0);
return;
}
for (int i = nums.length - 1; i > k; i--) {
if (nums[i] > nums[k]) {
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
break;
}
}
reverse(nums, k + 1);
}
static void reverse(int[] nums, int start) {
int end = nums.length - 1;
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
Tips:
- 代碼比較繁瑣，給你的不是集合工碾，只能自己寫一個反轉(zhuǎn)數(shù)組的函數(shù)弱睦，而且示例還可能出現(xiàn)重復(fù)元素，需要考慮邊界情況
- 時間復(fù)雜度為O(N)倚喂，不需要額外存儲空間
