企业官网建设流程全解析

目录

题目

思路

Code

题目

题目内容：

给定一个包含 n 个整数的数组 nums 和一个整数 k，需要将 nums 中的所有元素重新排列，生成一个新的序列。

数组下标从 0 开始，新序列中下标为 k-1 的元素和下标为 k 的元素不能相同。

请统计满足条件的不同排列数量，相同的数组排列只统计一次；如果无法构造出满足条件的数组，输出 0。

1 ≤ n ≤ 15，1 ≤ nums[i] ≤ 100，1 ≤ 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 位整数保存。

Code

from 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))

JS

const 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机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。