博文中会简要介绍Leetcode P0031题目分析及解题思路。
“Next Permutation”是一道比较经典的题目，考察的不仅是对数组结构的熟悉，也考察到了一些Math的功底。
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
这道题在寻找下一个在字母序上更大的排列。这里看到“字母序上更大的”需要想到什么样的排列是在字母序上最大的。显然，一个按字母序降序的排列是最大的。那么在数组上任意一段降序排列也一定是该段所有可能的排列上最大的，也就是说任何一段降序排列，不可能仅仅通过改变该段内部的顺序来得到一个更大字母序的排列。
但是如果我们将一个降序段中的某个字符x和这个降序段之前的升序段的最后一个字符y交换，再将交换后的降序段按升序排列，就能得到恰好比该降序段大的字符段，而这个字符x需要满足恰好比y大。
以下是Java的题解代码实现。
class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length <= 1)
return;
int start = -1, end = nums.length;
for (int idx=nums.length-1; idx>0; --idx) {
if (nums[idx] > nums[idx-1]) {
start = idx;
break;
}
}
if (start == -1) {
Arrays.sort(nums);
}
else {
int prev = start-1;
for (int idx=end-1; idx>=start; --idx) {
if (nums[idx] > nums[prev]) {
int temp = nums[idx];
nums[idx] = nums[prev];
nums[prev] = temp;
break;
}
}
// 线性交换
for (int idx=start; idx<(start+end)/2; ++idx) {
int temp = nums[idx];
nums[idx] = nums[end-(idx-start)-1];
nums[end-(idx-start)-1] = temp;
}
// Arrays.sort(nums, start, end);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (nums.size() <= 1)
return;
int start = -1, end = nums.size();
for (int itr=nums.size()-1; itr>=1; --itr) {
if (nums[itr] > nums[itr-1]) {
start = itr;
break;
}
}
if (start == -1)
sort(nums.begin(), nums.end());
else {
int prev = start-1, ptr = end-1;
for (; nums[ptr] <= nums[prev]; --ptr);
this->swap(&nums[prev], &nums[ptr]);
for (int idx=start; idx<(start+end)/2; ++idx) {
this->swap(&nums[idx], &nums[end-(idx-start)-1]);
}
}
}
private:
void swap(int *n1, int *n2) {
int temp = *n1;
(*n1) = *n2;
(*n2) = temp;
}
};