目录题目思路Code题目题目内容给定一个包含 n 个整数的数组 nums 和一个整数 k需要将 nums 中的所有元素重新排列生成一个新的序列。数组下标从 0 开始新序列中下标为 k-1 的元素和下标为 k 的元素不能相同。请统计满足条件的不同排列数量相同的数组排列只统计一次如果无法构造出满足条件的数组输出 0。1 ≤ n ≤ 151 ≤ nums[i] ≤ 1001 ≤ k ≤ n-1。输入描述第一行输入以英文逗号分隔的数组 nums。第二行输入限制索引 k。输出描述输出满足条件的不同数组排列数量。样例 1输入2,2,3 1输出2说明只有 [3,2,2] 和 [2,3,2] 两种不同排列满足下标 0 与下标 1 的元素不同。思路整体思路先计算多重集合的全部不同排列数量再减去两个限制位置放置相同数值的无效排列数量。第一步统计每个数值的出现次数。全部不同排列数等于 n 的阶乘除以各数值出现次数的阶乘乘积。第二步枚举可能同时放在两个限制位置的数值。只有出现至少两次的数值才能形成无效排列固定这两个位置后对剩余 n-2 个元素继续使用多重集合排列公式。第三步累加所有数值对应的无效排列数并用全部排列数减去无效排列数得到答案。不同数值形成的无效集合互不重叠因此不会重复扣除。正确性说明每个不同排列要么两个限制位置数值不同并被保留要么数值相同且唯一归属于该数值对应的无效集合二者完整且互斥。边界处理所有元素相同时答案为 0所有元素互不相同时答案为 n 的阶乘。所有位置在排列计数中对称因此合法 k 的具体取值不影响计数结果。复杂度分析设不同数值数量为 d按每个候选数值重新计算剩余频次需要 O(d²) 时间频次表和阶乘计算需要 O(n) 空间。由于 n≤15结果和中间阶乘均可使用 64 位整数保存。Codefrom collections import Counter from math import factorial import sys def solve(nums: list[int], k: int) - int: n len(nums) # counts 保存每个数值可用的副本数是去除重复排列时需要除掉的对称因素。 counts Counter(nums) # n! 先把所有元素视为不同再除以每组相同元素内部可交换的 count!。 total factorial(n) for count in counts.values(): total // factorial(count) # invalid 汇总两个限制位置取相同数值的排列不同数值对应的无效集合互不重叠。 invalid 0 for value, count in counts.items(): # 该数值不足两个时不可能同时占据 k-1 和 k 两个位置。 if count 2: continue # 固定两个位置都为 value 后只需排列剩余 n-2 个元素并消除其中的重复。 ways factorial(n - 2) for other_value, other_count in counts.items(): remaining other_count - 2 if other_value value else other_count ways // factorial(remaining) invalid ways # 每个去重排列要么合法要么唯一落入某个相同数值的无效集合因此直接相减不会漏算。 return total - invalid input sys.stdin.readline # 第一行按英文逗号拆分strip 同时兼容逗号两侧可能出现的空格。 nums [int(value.strip()) for value in input().strip().split(,)] k int(input().strip()) # k 只指定两个相邻位置所有位置在排列中对称所以合法范围内的 k 不改变计数公式。 print(solve(nums, k))JSconst fs require(fs); function factorial(value) { // 15! 虽仍在 Number 安全范围内BigInt 可让阶乘与整除全程保持明确的整数语义。 let result 1n; for (let factor 2n; factor BigInt(value); factor) { result * factor; } return result; } function solve(nums, k) { const n nums.length; // counts 记录每个数值的副本数用于消除相同元素互换造成的重复排列。 const counts new Map(); for (const value of nums) { counts.set(value, (counts.get(value) || 0) 1); } // 全部不同排列数为 n! 除以各数值出现次数的阶乘乘积。 let total factorial(n); for (const count of counts.values()) { total / factorial(count); } // invalid 汇总两个限制位置数值相同的排列各候选数值的无效集合互不重叠。 let invalid 0n; for (const [value, count] of counts) { // 少于两个副本的数值无法同时占据下标 k-1 和 k。 if (count 2) { continue; } // 固定两个位置为 value 后再按剩余频次计算 n-2 个元素的去重排列数。 let ways factorial(n - 2); for (const [otherValue, otherCount] of counts) { const remaining otherCount - (otherValue value ? 2 : 0); ways / factorial(remaining); } invalid ways; } // 全部排列扣除所有无效集合后剩余结果恰好是两个位置数值不同的答案。 return total - invalid; } // 第一行按英文逗号拆分trim 兼容数字两侧存在空格的输入。 const lines fs.readFileSync(0, utf8).trim().split(/\r?\n/); const nums lines[0].split(,).map((value) Number(value.trim())); const k Number(lines[1]); // k 只选择受限相邻位置位置对称性保证合法 k 不改变计数转字符串后输出完整大整数。 console.log(solve(nums, k).toString());【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
