axuhongbo的个人博客

https://leetcode-cn.com/problems/next-permutation/submissions/

算法介绍见 微信 程序员小灰

。。

挺坑的

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
      //  vector<int>ans;

        int len = nums.size();
       if(len<2)return;   //防止只有一个数
        int j = len-1;
        while(j>=1&&nums[j-1]>=nums[j])j--;  //  注意加上等于号，5 1 1情况
        int i = len-1;
        if(j>0) //不加会出现nums[-1]
        while(nums[i]<=nums[j-1]&&i>j)i--;  // 注意,i>j,加上等于号
//        cout<<"j: "<<j-1<<endl;
//        cout<<"i: "<<i<<endl;
        if(j==0){
            sort(nums.begin(),nums.end());
            return;
            //  return nums;
        }
        else if(i>=0&&j>=1){
            swap(nums[i],nums[j-1]);
            sort(nums.begin()+j,nums.end());
            //return nums;
        }
    }
};
int main(){
    Solution ss;
    int n;
    cin>>n;
    vector<int>nums;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        nums.push_back(num);
    }
    ss.nextPermutation(nums);
    for(int p:nums){
        cout<<p<<" ";
    }
}



//#include <iostream>
//#include<bits/stdc++.h>
//using namespace std;
//int board[500];
//const long long inf = 1e18;
//long long getsum(){
//  long long ans =0;
//  ans+=board[0]*board[1]*board[2]*board[3];
//  ans+=board[4]*board[5]*board[10]*board[11];
//  ans+=board[8]*board[9]*board[14]*board[15];
//  ans+=board[6]*board[7]*board[12]*board[13];
//  ans+=board[16]*board[17]*board[18]*board[19];
//  ans+=board[20]*board[21]*board[22]*board[23];
////  ans+=board[12]*board[13]*board[14]*board[15];
//
//  return ans;
//}
//void Swap(int a,int b,int c){
////    s
//}
//void Right(){
//
//}
//void Left(){
//}
//void Up(){
//}
//void Down(){
//}
//void Behind(){
//
//}
//void Front(){
//
//}
//int Ans  = 0;
//void DFS(int ){
//
//    long long sum = getsum();
//    if(sum>Ans){
//
//    }
//    if(tp==5)return ;
//
//}
//int main()
//{
//
//    for(int i=0;i<24;i++)
//        scanf("%d",&board[i]);
//
//    return 0;
//}