java 实现 蓝桥杯 算法提高 排列数
2024-08-27 20:12:54
问题描述
0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入格式
一行，包含一个整数n
输出格式
一行，包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
0 < n <= 10!
本题主要考查全排列中字典序的实现。关于如何实现字典序，这个是有专门的实现算法，具体实现原理，大家可以百度一下哟~
import java.util.Scanner;
public class Main {
public int count = 1; //用于计算当前已排列个数
public void swap(int[] A, int a, int b) {
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
//反转数组A中start~end区间的元素
public void reverseArray(int[] A, int start, int end) {
while(start < end) {
int temp = A[start];
A[start++] = A[end];
A[end--] = temp;
}
}
//判定数组A中是否有两个连续递增的元素
public boolean judgeArray(int[] A) {
for(int i = 1;i < A.length;i++) {
if(A[i - 1] < A[i])
return true;
}
return false;
}
//从数组A最后一位开始遍历，找出第一个出现A[i] < A[i + 1]的数组下标i
public int getFirstI(int[] A) {
int first = A.length - 1;
for(int i = first;i >= 1;i--) {
if(A[i - 1] < A[i]) {
first = i - 1;
break;
}
}
return first;
}
//扩展getFirstI功能，找出元素A[i]后面大于A[i]的最小元素下标
public int getFirstJ(int[] A) {
int j = getFirstI(A);
int valueI = A[j];
j++;
for(;j < A.length;j++) {
if(A[j] <= valueI) {
j = j - 1;
break;
}
}
if(j == A.length)
j = j - 1;
return j;
}
public void printResult(int[] A, int x) {
if(x == 1) {
for(int m = 0;m < A.length;m++)
System.out.print(A[m]);
return;
}
int i, j;
while(judgeArray(A)) { //字典序排序具体实现部分
i = getFirstI(A);
j = getFirstJ(A);
swap(A, i, j);
reverseArray(A, i + 1, A.length - 1);
count++;
if(count == x)
break;
}
for(int m = 0;m < A.length;m++)
System.out.print(A[m]);
return;
}
public static void main(String[] args) {
Main test = new Main();
int[] A = {0,1,2,3,4,5,6,7,8,9};
Scanner in = new Scanner(System.in);
int x = in.nextInt();
test.printResult(A, x);
}
}
最新文章
- UITableViewCell 单元格样式
- 【转】php curl 伪造IP来源的实例代码
- 程序员遇到Bug时的30个反应
- MacOS安装phpMyAdmin几点问题
- @Html.Partial,@Html.Action,@Html.RenderPartial,@Html.RenderAction区别 .（转）
- HTML前端技术(JS的使用,包括数组和字符串)
- Swift - 给表格添加编辑功能（删除，插入）
- Android KK台，联系人列表#集团放置A~Z之前
- LPC1788的IIC使用
- Cobbler自动化部署最佳实践
- Ubuntu下的终端多标签切换快捷键
- SMJobBless官方Demo笔记
- Web版记账本开发记录（三）开发过程遇到的问题小结2
- docker应用-6（mysql+mycat 搭建数据库集群）
- MongoDB运维心得（一）
- django之Model类
- ZooKeeper启动报错 JAVA_HOME is incorrectly set
- uploadify3.2.1 多文件上传总是只能上传一个文件
- 十图详解tensorflow数据读取机制
- Java注解(Annotation)用法：利用注解和反射机制指定列名导出数据库数据