OD华为机试 17

第K个全排列

描述

给定参数n，从1到n会有n个整数：1,2,3,…,n，这n个数字共有 n! 种排列。
按大小顺序升序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
1
2
3
4
5
6

给定 n 和 k，返回第 k 个排列。

输入描述:
输入两行，第一行为n，第二行为k，给定 n 的范围是 [1,9]，给定 k 的范围是[1,n!]。

输出描述:
输出排在第k位置的数字。

示例1：
输入

3
3
1
2

输出

213
1

说明
3的排列有123 132 213…，那么第3位置的为213

示例2 ：
输入

2
2
1
2

输出

21
1

说明
2的排列有12 21，那么第2位置的为21

法一

import java.util.*;

public class Main {
    public static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int num = sc.nextInt();
            int index = sc.nextInt();
            int[] arr = new int[num];
            for (int i = 0 ; i < num ; i++) {
                arr[i] = i + 1;
            }

            exchange(arr, 0, num - 1);

            list.sort((a, b) -> {
                return  b > a ? -1 : 1;
            });

            System.out.println(list.get(index - 1));
        }
    }
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    public static void exchange(int[] arr, int begin, int end) {
        if (begin == end) {
            String s = "";
            for (int i : arr) {
                s += i;
            }
            list.add(Integer.parseInt(s));
        } else {
            for (int i = begin ; i <= end ; i++) {
                swap(arr, begin, i);
                exchange(arr, begin + 1, end);
                swap(arr, begin, i);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44