题目描述补充

题目：排列序号Ⅰ

给定一个整数 n，返回从 1 到 n 的所有整数的排列序号。每个数字都有唯一的序号，序号的规则是基于字典序的排列。即，第一个排列是 "123..."，最后一个排列是 "n(n-1)...321"，并据此为它们分配序号从 1 到 n!。

示例：

输入：n = 3 输出：[1, 2, 3, 4, 5, 6] 解释：对于 n = 3，有6种排列：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。它们对应的序号分别为：[1, 2, 3, 4, 5, 6]。

要求：

• 编写一个函数来计算给定整数 n 的所有排列的序号。
• 考虑到效率，不要直接生成所有排列然后排序。

PHP 示例代码

function factorial($n) {
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}

function permutationIndex($nums) {
    $n = count($nums);
    $factorialCache = array_fill(0, $n, 0);
    $factorialCache[0] = 1;
    for ($i = 1; $i < $n; $i++) {
        $factorialCache[$i] = $factorialCache[$i - 1] * ($i + 1);
    }

    $index = 1;
    for ($i = 0; $i < $n; $i++) {
        $smaller = 0;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($nums[$j] < $nums[$i]) {
                $smaller++;
            }
        }
        $index += $smaller * $factorialCache[$n - $i - 1];
    }

    return $index;
}

// 示例用法
$nums = [1, 2, 3];
$n = count($nums);
$totalPermutations = factorial($n);
for ($i = 0; $i < $totalPermutations; $i++) {
    $perm = permute($nums); // 假设permute函数可以生成下一个排列
    echo permutationIndex($perm) . " ";
    // 注意：这里需要实现permute函数来生成下一个排列，但题目主要关注的是排列序号计算
}

// 注意：上述代码示例中的permute函数未给出，因为它不是本题的重点。
// 实际面试中，可能需要你专注于permutationIndex函数的实现。

Python 示例代码

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def permutationIndex(nums):
    n = len(nums)
    factorial_cache = [1] * n
    factorial_cache[0] = 1
    for i in range(1, n):
        factorial_cache[i] = factorial_cache[i - 1] * (i + 1)

    index = 1
    for i in range(n):
        smaller = sum(1 for j in range(i + 1, n) if nums[j] < nums[i])
        index += smaller * factorial_cache[n - i - 1]

    return index

# 示例用法
nums = [1, 2, 3]
total_permutations = factorial(len(nums))
# 这里省略了生成所有排列的代码，因为它不是本题的重点

JavaScript 示例代码

function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

function permutationIndex(nums) {
    const n = nums.length;
    const factorialCache = new Array(n).fill(0);
    factorialCache[0] = 1;
    for (let i = 1; i < n; i++) {
        factorialCache[i] = factorialCache[i - 1] * (i + 1);
    }

    let index = 1;
    for (let i = 0; i < n; i++) {
        let smaller = 0;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[i]) {
                smaller++;
            }
        }
        index += smaller * factorialCache[n - i - 1];
    }

    return index;
}

// 示例用法
const nums = [1, 2, 3];
const totalPermutations = factorial(nums.length);
// 注意：这里同样省略了生成所有排列的代码

码小课网站中有更多相关内容分享给大家学习，包括算法基础、数据结构与算法进阶等内容，可以帮助大家更好地掌握编程技能。