排列序列

Tips

题目类型: BackTracking

题目

给出集合 [1, 2, 3, ..., n], 其所有元素共有 n! 种排列.

按大小顺序列出所有排列情况, 并一一标记, 如当 n = 3 时, 所有排列为: "123", "132", "213", "231", "312", "321"

给定 n 和 k, 返回第 k 个排列.

提示:

• 1 <= n <= 9
• 1 <= k <= n!

示例

输入: n = 3, k = 3

输出: 213

输入: n = 4, k = 9

输出: 2314

题解

该题为 46. 全排列 的变种, 只不过是在全排列的过程中, 获取第 k 个数即可.

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
  let res = ''
  let count = 0

  const dfs = (track) => {
    if (track.length === n) {
      count += 1

      if (count === k) {
        res = track.join('')
        return
      }
    }

    for (let i = 1; i <= n; i++) {
      if (!track.includes(i)) {
        track.push(i)
        dfs(track)
        track.pop()
      }
    }
  }

  dfs([])

  return res
}

Rust

#[allow(unused)]
pub fn get_permutation(n: i32, k: i32) -> String {
    let mut res = String::new();
    let mut count = 0;
    let mut visited = vec![false; n as usize];

    // 注意 Rust 如果跟 JavaScript 的写法一样是会超时的
    // 需要引入 visited 函数规避一下
    dfs(n, k, &mut res, &mut count, &mut visited, &mut vec![]);

    res
}

fn dfs(
    n: i32,
    k: i32,
    res: &mut String,
    count: &mut i32,
    visited: &mut Vec<bool>,
    track: &mut Vec<i32>,
) {
    if track.len() == n as usize {
        *count += 1;

        if *count == k {
            *res = track.iter().map(|x| x.to_string()).collect::<String>();
            return;
        }
    }

    for i in 0..(n as usize) {
        if visited[i] {
            continue;
        }

        visited[i] = true;
        track.push(i as i32 + 1);
        dfs(n, k, res, count, visited, track);
        track.pop();
        visited[i] = false;
    }
}