43 贪心算法 -第K个排列

题 目 描 述

n ?个 字 共 有 n ！ 种 排 列 。

给 定 参 数 n ， 从 1 到 n 会 有 n 个 整 数 ： 123

按 大 小 顺 升 序 列 出 所 有 排 列 的 情 况 ，

并 己 当 n = 3 时 ，

所 有 排 列 如 下 ： “ 123 ” “ 132 ” “ 213 ” “ 231 ” “ 312 ， “ 321 ”

给 定 n 和 k ， 返 回 第 k 价 葬 列 。

输 入 描 述 ，

第 一 行 为 n ，

第 二 行 为 k ， 给 定 n 的 范 围 是 [ 1 ， 9 ] 给 定 k 的 范 围 是 [ 1 ,n 刂 。

输 出 描 述

输 出 排 在 k 位 首 的 数 字 。

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
  static int[] fact;
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
 
    int n = sc.nextInt();
    int k = sc.nextInt();
 
    fact = new int[n + 1];
    fact[1] = 1;
    for (int i = 2; i <= n; i++) {
      fact[i] = fact[i - 1] * i;
    }
 
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) arr[i] = i + 1;
 
    System.out.println(getNK(n, k, arr));
  }
 
  public static String getNK(int n, int k, int[] arr) {
    if (n == 1) return "1";
 
    int f = fact[n - 1];
    int prefix = arr[(k - 1) / f];
    k %= f;
    k = k == 0 ? f : k;
 
    arr = Arrays.stream(arr).filter(ele -> ele != prefix).toArray();
 
    if (k == 1) {
      StringBuilder sb = new StringBuilder();
      for (int v : arr) sb.append(v);
      return prefix + sb.toString();
    } else {
      return prefix + getNK(n - 1, k, arr);
    }
  }
}