华为OD机试_2025 B卷_最小循环子数组（Python，100分）（附详细解题思路）

题目描述

给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。

输入描述
第一行输入数组中元素个数n，1 ≤ n ≤ 100000

第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10

输出描述
输出最小的子数组的数字序列，以空格分割；

备注
数组本身是其最大的子数组，循环1次可生成的自身；

用例

核心解题思路

本题要求找出数组能否由某个子数组重复多次拼接而成，并输出最小的子数组。例如，数组 [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 math

n = 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 = True
        for i in range(n):
            if nums[i] != nums[i % k]:
                valid = False
                break
        if 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 = True
    for i in range(n):
        if nums[i] != nums[i % k]:
            valid = False
            break

• 逻辑：逐个检查每个元素是否满足 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. 生成因数 [1, 3, 9]。
2. 检查 k=1：发现 nums[1] != nums[0]（2 ≠ 1），不满足。
3. 检查 k=3：所有元素均满足 nums[i] = nums[i % 3]，返回 [1, 2, 1]。

总结

通过预处理所有可能的子数组长度，并逐一验证重复规则，可以在合理时间内找到最小的满足条件的子数组。关键点在于因数的生成和高效验证每个候选长度的有效性。