最小循环子数组 - 华为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次拼接而成

题解

这道题目属于数组模式匹配类问题，具体来说是寻找数组的最小循环节（最小重复子数组）。这类问题通常可以通过字符串匹配算法或数学方法解决。

解题思路

核心思路

1. 问题转化：将原问题转化为寻找数组的最小周期（最小重复子数组长度）。如果数组可以由某个子数组重复多次构成，那么这个子数组的长度必须是数组长度的约数。
2. 关键观察：
   • 最小重复子数组的长度必须是数组长度的约数
   • 每个元素出现的次数必须是重复次数的整数倍
   • 需要验证候选子数组是否能通过重复构成原数组
3. 优化策略：
   • 先统计每个数字的出现频率
   • 最小重复次数是所有数字出现次数的最大公约数
   • 从小到大枚举可能的子数组长度进行验证

算法选择

使用枚举+验证的方法：

1. 枚举所有可能的子数组长度（数组长度的约数）
2. 对于每个候选长度，验证是否能通过重复构成原数组

Python

from collections import Counter


def 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:
            continue

        if any(v % sub_length for v in cnt.values()):
            continue

        if check_repeated(nums, sub_length):
            result = sub_length
            break

    # 输出结果子数组
    print(' '.join(map(str, nums[:result])))


if __name__ == "__main__":
    main()

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏