2014
11-19

# LeetCode-Next Permutation[数组]

### Next Permutation

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, do not allocate 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,31,3,2
3,2,11,2,3
1,1,51,5,1

\begin{center}
\includegraphics[width=360pt]{next-permutation.png}\\
\figcaption{下一个排列算法流程}\label{fig:permutation}
\end{center}

// LeetCode, Next Permutation
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
void nextPermutation(vector<int> &num) {
next_permutation(num.begin(), num.end());
}

template<typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last) {
// Get a reversed range to simplify reversed traversal.
const auto rfirst = reverse_iterator<BidiIt>(last);
const auto rlast = reverse_iterator<BidiIt>(first);

// Begin from the second last element to the first element.
auto pivot = next(rfirst);

// Find pivot, which is the first element that is no less than its
// successor.  Prev is used since pivort is a reversed_iterator.
while (pivot != rlast && *pivot >= *prev(pivot))
++pivot;

// No such elemenet found, current sequence is already the largest
// permutation, then rearrange to the first permutation and return false.
if (pivot == rlast) {
reverse(rfirst, rlast);
return false;
}

// Scan from right to left, find the first element that is greater than
// pivot.
auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));

swap(*change, *pivot);
reverse(rfirst, pivot);

return true;
}
};


1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 不考虑最后将结果排序的话，快排的时间复杂度是O(N) ，而堆排的是O(N*logK),这样比较看，快排快

3. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！