LeetCode-Go 题解 1175Prime Arrangements 质数排列的组合计数与打表法实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode 1175 要求为从 1 到 n 的整数设计排列方案使得所有质数恰好落在质数索引1-indexed上并返回方案总数对10^9 7取模的结果。本文以 leetcode/1175.Prime-Arrangements/README.md 为骨架结合仓库内 1175. Prime Arrangements.go 的源码实现与 1175. Prime Arrangements_test.go 的测试用例完整讲解质数个数统计、双独立全排列组合计数、阶乘取模三个核心步骤帮助读者掌握这类「位置约束 全排列计数」题目的通用解法并能直接运行仓库代码验证结果。题目理解质数必须放在质数索引上原题描述Return the number of permutations of1tonso that prime numbers are at prime indices (1-indexed).回忆质数定义一个整数是质数当且仅当它大于 1且不能写成两个都比它小的正整数的乘积。由于答案可能很大返回答案对10^9 7取模的结果。输入输出示例示例 1Input: n 5 Output: 12 Explanation: 例如 [1,2,5,4,3] 是一个合法排列但 [5,2,3,4,1] 不合法因为质数 5 被放在了索引 1索引从 1 开始索引 1 不是质数索引。示例 2Input: n 100 Output: 682289015约束条件1 n 100题意解析把 1 到 n 这 n 个数摆放到 1 到 n 这 n 个位置上。位置按照下标索引从 1 开始分为两类质数索引2、3、5、7、11、……1 不是质数索引 1 不属于质数索引非质数索引1、4、6、8、9、……题目要求所有质数必须放置在质数索引上所有非质数必须放置在非质数索引上。求满足该约束的全排列总数。核心思路把约束拆成两个独立的排列问题这是本题最关键的转化。假设 1 到 n 中一共有primeCount个质数那么非质数有n - primeCount个。由于质数只能放进质数索引非质数只能放进非质数索引两类元素被完全隔离质数共有primeCount个质数索引也恰好有primeCount个索引 2、3、5、7……在 1 到 n 范围内恰好对应前primeCount个质数因此质数在这些质数索引上的摆放方式数为primeCount!非质数共有n - primeCount个剩余的非质数索引也恰好有n - primeCount个因此非质数的摆放方式数为(n - primeCount)!。两类摆放互不影响根据乘法原理最终答案为答案 primeCount! × (n - primeCount)! (mod 10^9 7)以n 5验证1 到 5 中质数为 2、3、5 共 3 个非质数为 1、4 共 2 个。质数只能放在索引 2、3、5 上共3! 6种非质数放在索引 1、4 上共2! 2种。总数为6 × 2 12与示例输出一致。算法步骤打表 二分定位质数个数 阶乘取模由于n 100仓库 1175. Prime Arrangements.go 采用了「打表法」先把 100 以内的全部质数预置为全局表再用二分快速定位「小于等于 n 的质数个数」最后分别计算两个阶乘并取模。步骤一质数表打表100 以内共有 25 个质数var primes []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}该表按升序排列且覆盖了约束范围1 n 100内的所有可能取值。步骤二用二分搜索定位质数个数primeCount : sort.Search(25, func(i int) bool { return primes[i] n })sort.Search在长度为 25 的表上二分查找第一个满足primes[i] n的下标。由于表严格升序该下标恰好等于「小于等于 n 的质数个数」。例如n 5时第一个大于 5 的元素是 7下标 3因此primeCount 3。相比线性扫描二分定位只消耗O(log 25)次比较在单次查询场景下也保持了打表法应有的简洁与高效。步骤三两个独立全排列计数的阶乘与取模return factorial(primeCount) * factorial(n-primeCount) % 1000000007factorial(primeCount)质数在质数索引上的全排列数factorial(n-primeCount)非质数在非质数索引上的全排列数两者相乘后对1000000007即10^9 7取模防止中间结果溢出int范围并满足题目取模要求。源码级实现解析仓库中 1175. Prime Arrangements.go 的完整实现如下package leetcode import sort var primes []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} func numPrimeArrangements(n int) int { primeCount : sort.Search(25, func(i int) bool { return primes[i] n }) return factorial(primeCount) * factorial(n-primeCount) % 1000000007 } func factorial(n int) int { if n 1 || n 0 { return 1 } return n * factorial(n-1) % 1000000007 }递归阶乘中的取模细节factorial在每一层递归都执行n * factorial(n-1) % 1000000007这意味着每一步乘法结果都先取模再进入下一层避免n!在中间阶段膨胀到溢出 64 位整数递归基factorial(0) factorial(1) 1n 100时最坏递归深度为 100不会引发栈溢出。对质数个数边界情况的处理当n 1时primeCount 0答案为factorial(0) × factorial(1) 1即只有排列[1]正确当n 2时质数只有 2 一个答案为1! × 1! 1唯一合法排列是[1, 2]当n 3时质数为 2、3 两个质数索引为 2、3答案为2! × 1! 2。这些边界情况均被组合公式自然覆盖无需特判。测试用例与运行验证仓库内 1175. Prime Arrangements_test.go 给出了三组测试数据n期望输出5129975763854100682289015其中n 99与n 100两个用例都涉及大数阶乘取模用于检验模运算在primeCount! × (n - primeCount)!场景下的正确性。运行单题测试目录名包含空格与点号需要为路径加引号go test ./leetcode/1175.Prime-Arrangements/... -v若需在仓库范围内统一跑测试并生成覆盖率报告可使用仓库根目录的 gotest.shbash gotest.sh该脚本会以-covermodeatomic一次性对./leetcode/...下所有包生成覆盖率文件coverage.txt与本仓库「100% test coverage」的目标保持一致。手工验证示例 1n 5统计质数2、3、5共 3 个factorial(3) 6factorial(2) 26 × 2 12输出 12。✅手工验证示例 2n 100100 以内共 25 个质数恰好是打表数组长度答案为25! × 75! mod 1000000007 682289015与测试期望一致。✅复杂度分析时间复杂度sort.Search二分定位为O(log 25)两次阶乘递归为O(primeCount n - primeCount) O(n)总时间复杂度O(n)空间复杂度递归栈深度为O(n)质数表为固定常量总空间复杂度O(n)递归栈加上常量级表空间。由于约束1 n 100该复杂度在题设范围内表现良好即便放大到更大的n只要质数表随之扩充算法结构依然成立。延伸思考1. 为什么两类排列可以独立相乘本题的约束质数只在质数索引上没有对质数之间的相对顺序、非质数之间的相对顺序做任何额外限制因此「选位置」与「排顺序」被完全解耦直接套用排列数公式即可。若题目进一步约束质数必须按升序摆放答案就会退化为C(primeCount, primeCount) × (n - primeCount)!——对比之下更容易理解本题乘法公式的来源。2. 打表法适用的场景边界打表法适合「查询域有限且可枚举」的问题。本题n 100100 以内质数可手工枚举共 25 个如果n的范围扩大到 10^6 量级则更适合在函数内用埃氏筛Sieve of Eratosthenes动态统计质数个数而不是维护一张超长静态表。从仓库实现看静态表 二分的组合在本题约束下是最直观、最不易出错的选择。3. 取模运算的位置公式中两处阶乘分别取模后再相乘取模是基于模运算的分配律(a mod m) × (b mod m) mod m a × b mod m。这是所有「答案很大需取模」的组合计数题的通用写法可避免任何一次中间乘法溢出 64 位整数。小结LeetCode 1175 的解法链条可以总结为三步拆解约束质数 ↔ 质数索引、非质数 ↔ 非质数索引互不干扰组合计数答案为primeCount! × (n - primeCount)!打表 二分 递归阶乘取模在n 100的约束下用最简代码完成统计与计算。仓库源码 1175. Prime Arrangements.go 仅用十余行代码就完整实现了上述思路配合 1175. Prime Arrangements_test.go 中的三组用例可以快速验证「质数个数统计 → 阶乘取模」这一核心逻辑是理解组合计数类题目的经典范本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考