題目:從 1-9 選取 N 個數字組成不重復 N 位數,按從小到大編號。給定任意一個合法數 M,求其排名(1-based)。
例:N=3,M=213 → 全排列 [123,132,213,231,312,321] → 排名 3。
不生成全排列,直接用組合數學計算:
cnt。cnt × (剩餘位數)!`。// 階乘預計算
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 計算」,邏輯等價但實現較繁瑣。本版本直接逐位統計未用較小數字,更直觀、通用、易擴展(支持任意數字集合)。
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;
}
全排列排名問題本質是因子進制(因子數制)編碼。掌握「逐位統計未用較小元素 × 階乘」模板,可秒殺所有類似題目,且無需生成排列,時間空間極優。