题目描述

升序的话也包含在实现方法中，，是一个思考过程

题目模型

模型就是对n个数字按照字典序进行排列，以当前给出的某一排列为基准，向后数m个的排列，输出排列结果

算法

1.手动实现c++中的next_permutation()函数
2.实现原理

3.注意数组下标越界的问题，从1开始

package day;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class 火星人 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(bufferedReader.readLine());
    int a[]=new int [1+n];
    int m=Integer.parseInt(bufferedReader.readLine());
    String p[]=bufferedReader.readLine().split(" ");
    for(int i=1;i<=n;i++){
        a[i]=Integer.parseInt(p[i-1]);
    }

    while(m>0){
        int k=n;
        while(a[k-1]>a[k])k--;
        //找到降序排列的起点位置
        //寻找比k-1的位置大的最小的数字
        int t=k;
        while( t <n && a[k-1] < a[t+1] ) t++;

        int tem=a[t];
        a[t]=a[k-1];
        a[k-1]=tem;

        ArrayList<Integer> alArrayList= new ArrayList<Integer>();
        for(int i=n;i>=k;i--){
            alArrayList.add(a[i]);
        }
        for(int i=k;i<=n;i++){
            int te=alArrayList.get(i-k);
            a[i]=te;
        }
        m--;
    }
    for(int i=1;i<=n;i++){
        System.out.print(a[i]+" ");
    }

    }

}