题目大意:
把 $1∼n$ 这 $n$ 个整数排成一行后随机打乱顺序,输出所有可能的次序。
对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。
解题方法:
我三道题不用递归挑战成功!!!
我们这题需要用到 $next\_permutation$ 函数。
具体函数操作是给一个序列,输出他的下一个排列。
里面填的东西语法和 $sort$ 是一样的。
这样就完事了
关于这个时间复杂度我在底下说,先给代码。
完整代码,时间复杂度:$O(n\log n n!)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int n, m, cnt;
int a[N];
int p(int x) {
int res = 1;
for (int i = 1; i <= x; i ++ ) res *= i;
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) a[i] = i;
for (int i = 1; i <= p(n); i ++ ) {
for (int i = 1; i <= n; i ++ ) cout << a[i] << " ";
cout << endl;
next_permutation(a + 1, a + n + 1);
}
return 0;
}
关于时间复杂度的补充说明:
我们想知道时间复杂度,先要知道它的原理,具体分为四步:
要先找到一个下降点——如下图:
图中对于一个数值越大,则高度越高。
图中用蓝色框起来的点是最高点,在蓝色框之后(包括蓝框点)显然已经是最大的排列,想要再增加只能动前面的。
$O(n)$
所以我们在蓝框点(还是包括蓝框)以后找比绿框点大的且最接近的。
$O(\log n)$
接着我们把找到的点换到绿框的位置。
$O(1)$
最后,我们把后面的东西排序(因为已经到了后面排列,就一定要让后面的最小才能保证是下一个排列)
$O(n\log n)$
因为还有枚举的 $O(n!)$,所以最后时间复杂度为 $O(n \log n n!)$
$next\_permutation$??
对啊
$next_permutation$娃哈哈
是$next$_$permutation$,不是$next_permutation$
我搞了半天转义,终于好了
所以您是怎么干的,我是
next_permutation
$next_permutation$
不管用啊
$next\underline{~}permutation$
$next\underline{~}permutation$
我是\,打出来就没了
\
\
我打的是两个\,打出来就没了