9.13华为OD机试真题 新系统 – 受限序列重排 (JavaPyCC++JsGo)
2026 华为OD机试真题9月13日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
给定一个包含 n 个整数的数组 nums 和一个整数 k，你需要将数组 nums 中的所有元素重新排列，生成一个新的序列数组，其中下标第 k−1 个元素和下标第 k 个元素不能数值相同。
请统计重新排列后符合条件的数组个数（相同的数组排列需去重统计）；如果无法构造出满足上述所有条件的数组，结果为 0。
2026 华为OD机试真题9月13日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
本题为核心代码模式，你需要实现函数 countArrangements(nums, k)。
参数 nums 为一个整数数组，长度 n（1≤n≤15），元素 nums[i]（1≤nums[i]≤100）。
参数 k（1≤k≤n−1）为一个整数，表示限制索引。
为了便于在线判题，第一行输入以英文逗号分隔的数组元素，第二行输入整数 k。
输出描述
输出符合条件的不同数组个数；无法构造出满足条件的数组时输出 0。
示例1
输入
2,2,3
1输出
2说明
只存在
[3,2,2]和[2,3,2]两种合法情况。
解题思路
核心思想
直接生成所有排列会产生大量重复状态，最坏需要枚举 15! 种顺序。题目只限制两个指定位置上的数值不能相同，因此可以使用多重集合排列计数，先求全部不同排列数，再减去两个位置数值相同的排列数。
设数值 x 出现 cnt[x] 次，数组长度为 n。
全部去重排列数为：
total = n! / ∏cnt[x]!把两个指定位置看成有顺序的位置对。从 n 个元素中选择两个元素放入这两个位置，共有 n × (n - 1) 种有序选择。对于数值 x，两个位置都选择 x 的方式数为 cnt[x] × (cnt[x] - 1)。因此两个位置数值相同的有序选择总数为：
samePairs = ∑cnt[x] × (cnt[x] - 1)两个位置数值不同的比例为：
(n × (n - 1) - samePairs) / (n × (n - 1))最终合法排列数为：
answer = total × (n × (n - 1) - samePairs) / (n × (n - 1))由于元素取值范围为 1 到 100，可以使用长度为 101 的频次数组代替哈希表，使统计结构更简单、访问开销更低。k 只决定受限制的是哪两个相邻位置；所有位置在排列计数中是对称的，因此合法排列总数与 k 的具体取值无关。
算法步骤
- 使用频次数组统计每个数值的出现次数。
- 预处理
0!到n!。 - 用
n!依次除以每个频次的阶乘，得到全部去重排列数total。 - 累加每个数值贡献的
cnt[x] × (cnt[x] - 1)，得到samePairs。 - 根据组合比例计算并返回合法排列数。
复杂度分析
设数组长度为 n，数值范围大小为 V，本题 V=100。
- 时间复杂度：
O(n + V)。 - 空间复杂度：
O(n + V)，用于阶乘数组和频
