华为OD机试_2025 B卷_最小循环子数组（Python，100分）（附详细解题思路）
题目描述
给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。
输入描述
第一行输入数组中元素个数n，1 ≤ n ≤ 100000
第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10
输出描述
输出最小的子数组的数字序列，以空格分割；
备注
数组本身是其最大的子数组，循环1次可生成的自身；
用例
| 输入 | 9 1 2 1 1 2 1 1 2 1 |
| 输出 | 1 2 1 |
| 说明 | 数组[1,2,1,1,2,1,1,2,1] 可由子数组[1,2,1]重复循环3次拼接而成 |
核心解题思路
本题要求找出数组能否由某个子数组重复多次拼接而成，并输出最小的子数组。例如，数组 [1,2,1,1,2,1,1,2,1] 可以由子数组 [1,2,1] 重复3次生成。关键在于如何高效验证所有可能的子数组长度，并找到满足条件的最小值。
解题步骤详解
1. 理解子数组的特性
- 长度约束：子数组的长度
k必须是原数组长度n的因数。例如，原数组长度为9时，可能的子数组长度为1、3、9。 - 重复规则：原数组的第
i个元素必须等于子数组中第i % k个元素。
2. 枚举所有可能的子数组长度
- 因数的生成：遍历所有可能的因数。例如，当
n=9时，因数为[1, 3, 9]。 - 验证候选子数组：对每个候选长度
k，检查原数组是否满足nums[i] == nums[i % k]。
3. 优先选择最小长度
从最小的候选长度开始遍历，一旦找到满足条件的长度的子数组，即可立即返回结果。
完整代码实现
import mathn = int(input())
nums = list(map(int, input().split()))def find_min_repeating_subarray():if n == 0:return []# 生成所有可能的因数，从小到大排序factors = set()for i in range(1, int(math.isqrt(n)) + 1):if n % i == 0:factors.add(i)factors.add(n // i)sorted_factors = sorted(factors)# 检查每个候选k是否满足条件for k in sorted_factors:valid = Truefor i in range(n):if nums[i] != nums[i % k]:valid = Falsebreakif valid:return nums[:k]return nums # 保底，返回整个数组（虽然题目中说必定存在）result = find_min_repeating_subarray()
print(' '.join(map(str, result)))
关键代码解析
1. 因数生成
factors = set()
for i in range(1, int(math.isqrt(n)) + 1):if n % i == 0:factors.add(i)factors.add(n // i)
- 目标：生成
n的所有因数。例如，n=9的因数为{1, 3, 9}。 - 方法：遍历
1到sqrt(n)，若i是因数，则n//i也是因数。
2. 验证子数组
for k in sorted_factors:valid = Truefor i in range(n):if nums[i] != nums[i % k]:valid = Falsebreak
- 逻辑：逐个检查每个元素是否满足
nums[i] == nums[i % k]。 - 优化：若任一元素不满足，立即终止当前候选长度的检查。
时间复杂度分析
- 因数生成：O(√n)，因为遍历到
sqrt(n)。 - 验证子数组：O(n * d(n))，其中
d(n)是n的因数数量。对于n ≤ 1e5，d(n)较小（如d(1e5) = 100），总时间为1e5 * 100 = 1e7，可以接受。
示例验证
以输入 9 1 2 1 1 2 1 1 2 1 为例：
- 生成因数
[1, 3, 9]。 - 检查
k=1：发现nums[1] != nums[0]（2 ≠ 1），不满足。 - 检查
k=3：所有元素均满足nums[i] = nums[i % 3]，返回[1, 2, 1]。
总结
通过预处理所有可能的子数组长度，并逐一验证重复规则，可以在合理时间内找到最小的满足条件的子数组。关键点在于因数的生成和高效验证每个候选长度的有效性。