手动模拟next_permutation()
-
每次遍历数组找到需要交换的元素,是O(n)的;一共求m次next_permutation,故复杂度O(n*m)
-
替换完a[i-1]和a[j-1]之后,要使得被替换元素之后的元素从小到达升序排列(相当于高位变大,低位要变成最小,如3421到4123,而不是3421到4321),但可以发现,被替换元素之后一定是逆序排列,逆置reverse一下即可,无需排序。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--)
{
int i = n-1; //从最后开始
while(a[i-1] > a[i]) i--; //找到第一个能增大字典序的位置,要把i-1处的元素替换成比他大的最小元素
int j = i; //从i处开始向后,找到大于a[i-1]的最小元素(i-1后面必是逆序序列)
while(a[j] > a[i-1]) j++; //让j指向第一个比a[i-1]小的元素,则j-1指向比a[i-1]大的最小元素
swap(a[i-1],a[j-1]); //替换,增大字典序
reverse(a + i, a + n); //i到n-1元素逆置
}
for(int i=0;i<n;i++) cout<<a[i]<<' ';
return 0;
}
直接吃现成米饭(真香)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,m;
int a[N];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--) next_permutation(a,a+n); //往后求m次全排列
for(int i=0;i<n;i++) cout<<a[i]<<' ';
return 0;
}