[leetcode]Next Permutation
2614 ワード
次の組み合わせの数.配列内の一部のソートがあるので、c++のほうが自然です.アルゴリズムは簡単で、末尾から先頭に順番に合わないものを探して、それから交換して、それから後ろのソートをします.交換はpivotよりちょうど大きい要素を見つけなければなりません.いくら小さいので、交換すれば、これらの順序はすでに並んでいます.
2回目:前の方法でsortを使ったが、実はO(n)ではない.C++ライブラリの中の方法はreverseを使うので、swapの後、後半は実はちょうど逆の順序で、このようにreverseはsortに相当します.sortを使えば、Annieの書き方はもっと簡潔です.https://github.com/AnnieKim/LeetCode/blob/master/NextPermutation.h
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void nextPermutation(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int idx = num.size() - 1;
bool inorder = true;
while ( idx > 0) {
if ((num[idx] > num[idx-1])) {
inorder = false;
break;
}
idx--;
}
if (inorder) {
sort(num.begin(), num.end());
return;
}
idx--;
// idx is the number need to be exchanged
int minIdx = INT_MAX;
for (int i = idx+1; i < num.size(); i++) {
if (num[i] > num[idx]) {
if (minIdx == INT_MAX || num[i] < num[minIdx])
{
minIdx = i;
}
}
}
swap(num, idx, minIdx);
sort(num.begin() + idx + 1, num.end());
}
void swap(vector<int> &num, int a, int b) {
int tmp = num[a];
num[a] = num[b];
num[b] = tmp;
}
};
2回目:前の方法でsortを使ったが、実はO(n)ではない.C++ライブラリの中の方法はreverseを使うので、swapの後、後半は実はちょうど逆の順序で、このようにreverseはsortに相当します.sortを使えば、Annieの書き方はもっと簡潔です.https://github.com/AnnieKim/LeetCode/blob/master/NextPermutation.h
class Solution {
public:
void nextPermutation(vector<int> &num) {
int i = num.size() - 1;
while (i > 0 && num[i] <= num[i-1])
i--;
if (i == 0)
{
reverse(num, 0, num.size()-1);
return;
}
int pivot = num[i-1];
int idx = -1;
for (int j = num.size()-1; j >= i; j--)
{
if (idx == -1 && num[j] > pivot)
{
idx = j;
}
else if (idx != -1 && num[j] > pivot && num[j] < num[idx])
{
idx = j;
}
}
swap(num, i-1, idx);
reverse(num, i, num.size()-1);
}
void reverse(vector<int> &num, int l, int r)
{
while (l < r)
{
swap(num, l, r);
l++;
r--;
}
}
void swap(vector<int> &num, int i, int j)
{
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
};