最小循环子数组 - 华为OD统一考试（Python题解）
华为OD机试题库《C++》限时优惠 9.9
华为OD机试题库《Python》限时优惠 9.9
华为OD机试题库《JavaScript》限时优惠 9.9
针对刷题难，效率慢，我们提供一对一算法辅导， 针对个人情况定制化的提高计划（全称1V1效率更高）。
看不懂有疑问需要答疑辅导欢迎私VX： code5bug
题目描述
给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。
输入描述
第一行输入数组中元素个数n，1 <= n <= 100000
第二行输入数组的数字序列nums，以空格分割，0 <= nums[i] <= 10
输出描述
输出最小的子数组的数字序列，以空格分割;
备注
数组本身是其最大的子数组，循环1次可生成的自身
示例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次拼接而成
题解
这道题目属于数组模式匹配类问题，具体来说是寻找数组的最小循环节（最小重复子数组）。这类问题通常可以通过字符串匹配算法或数学方法解决。
解题思路
核心思路
- 问题转化：将原问题转化为寻找数组的最小周期（最小重复子数组长度）。如果数组可以由某个子数组重复多次构成，那么这个子数组的长度必须是数组长度的约数。
- 关键观察：
- 最小重复子数组的长度必须是数组长度的约数
- 每个元素出现的次数必须是重复次数的整数倍
- 需要验证候选子数组是否能通过重复构成原数组
- 优化策略：
- 先统计每个数字的出现频率
- 最小重复次数是所有数字出现次数的最大公约数
- 从小到大枚举可能的子数组长度进行验证
算法选择
使用枚举+验证的方法：
- 枚举所有可能的子数组长度（数组长度的约数）
- 对于每个候选长度，验证是否能通过重复构成原数组
Python
from collections import Counterdef check_repeated(nums, sub_length):"""检查数组nums是否由长度为sub_length的子数组重复构成"""n = len(nums)return all(nums[i] == nums[j] for i in range(sub_length) for j in range(i + sub_length, n, sub_length))def main():n = int(input())nums = list(map(int, input().split()))cnt = Counter(nums)result = n # 默认结果是整个数组# 枚举所有可能的子数组长度for sub_length in range(1, n // min(cnt.values()) + 1):if n % sub_length != 0:continueif any(v % sub_length for v in cnt.values()):continueif check_repeated(nums, sub_length):result = sub_lengthbreak# 输出结果子数组print(' '.join(map(str, nums[:result])))if __name__ == "__main__":main()
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏