leetcode

leetcode 60题

Posted by franki on June 23, 2021

leetcode 60题 排列序列

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

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

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

示例1

输入：n = 3, k = 3
输出："213"

示例2

输入：n = 4, k = 9
输出："2314"

示例3

输入：n = 3, k = 1
输出："123"

思路

每次计算开始和结束的位置

代码

const constArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const getNum = function (n, k, arr) {
    let total = constArr.slice(0, n - 1).reduce((total, now) => {
        return total * now;
    }, 1);

    let end = k % total;
    let start = Math.floor(k / total);
    return {
        end: end,
        start: start
    }
}
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
    let newArr = constArr.slice(0, n);
    let str = '';
    let result = getNum(n, k - 1, newArr);
    str += newArr.splice(result.start, 1)[0];
    while (result.end !== 0) {
        result = getNum(--n, result.end, newArr);
        str += newArr.splice(result.start, 1)[0];
    }
    str += newArr.join('');
    return str;
};

复杂度分析:

  • 时间复杂度: O(N)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS