萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 算法題:求 1-9 不重復 N 位數在全排列中的字典序排名

題目:從 1-9 選取 N 個數字組成不重復 N 位數,按從小到大編號。給定任意一個合法數 M,求其排名(1-based)。
例:N=3,M=213 → 全排列 [123,132,213,231,312,321] → 排名 3。

核心思路:逐位計算「比當前前綴小的排列數」

不生成全排列,直接用組合數學計算:

  1. 對每一位,統計「未使用且小於當前數字」的可選數字個數 cnt。
  2. 該位貢獻的排名增量 = cnt × (剩餘位數)!`。
  3. 累加所有位貢獻,最後 +1 得到排名。

完整實現

// 階乘預計算
const fact = [1];
for (let i = 1; i <= 9; i++) fact[i] = fact[i-1] * i;

function getRank(numStr) {
  const digits = numStr.split('').map(Number);
  const n = digits.length;
  const used = new Array(10).fill(false); // 1-9
  let rank = 1; // 1-based
  
  for (let i = 0; i < n; i++) {
    const cur = digits[i];
    // 統計未用且小於 cur 的數字個數
    let cnt = 0;
    for (let d = 1; d < cur; d++) if (!used[d]) cnt++;
    
    rank += cnt * fact[n - i - 1];
    used[cur] = true; // 標記已用
  }
  return rank;
}

// 測試
console.log(getRank('213'));   // 3
console.log(getRank('123'));   // 1
console.log(getRank('231'));   // 4
console.log(getRank('312'));   // 5
console.log(getRank('4321'));  // 24
console.log(getRank('21'));    // 2
console.log(getRank('1'));     // 1

原始作者思路對比

原文採用「先構建每位的相對排名數組 a[],再調用 getAll 計算」,邏輯等價但實現較繁瑣。本版本直接逐位統計未用較小數字,更直觀、通用、易擴展(支持任意數字集合)。

複雜度分析

  • 時間:O(N²) —— N≤9 時極快,N=9 僅 81 次循環。
  • 空間:O(1) —— 固定大小輔助數組。

擴展:任意字符集合的字典序排名

function rankInPermutations(arr, sortedChars) {
  // arr: 目標排列數組
  // sortedChars: 所有可用字符的有序數組
  const used = new Set();
  let rank = 1;
  const fact = [1];
  for (let i = 1; i <= sortedChars.length; i++) fact[i] = fact[i-1] * i;
  
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    const idx = sortedChars.indexOf(cur);
    let cnt = 0;
    for (let j = 0; j < idx; j++) if (!used.has(sortedChars[j])) cnt++;
    rank += cnt * fact[sortedChars.length - i - 1];
    used.add(cur);
  }
  return rank;
}

總結

全排列排名問題本質是因子進制(因子數制)編碼。掌握「逐位統計未用較小元素 × 階乘」模板,可秒殺所有類似題目,且無需生成排列,時間空間極優。

copyright © 萬盛學電腦網 all rights reserved