面试遇阻：如何查找数组的最小循环长度？

嘿，针对你提出的数组最小循环长度问题，我来梳理下可行的思路，先结合你的示例明确问题定义，再聊聊具体的实现方法，也会回应你尝试过的两种思路～

先明确问题定义 #

根据你的示例，这里的最小循环长度指的是：找到最短的子数组长度k，使得整个原数组可以看作是这个长度为k的子数组（循环节）重复若干次，再加上该循环节的前r个元素（0 ≤ r < k）。如果不存在这样的k < n（n是原数组长度），则最小循环长度就是n本身。

对应你的示例：

• [1,2,1,2]：k=2，循环节[1,2]重复2次刚好覆盖整个数组
• [1,2,1,2,1]：k=2，循环节[1,2]重复3次后取前5个元素（刚好是[1,2,1,2,1]）
• [1,2,1,2,3]：不存在k<5的循环节能满足条件，所以k=5
• [1,2,1,2,1,1,2]：k=5，循环节[1,2,1,2,1]重复1次后取前2个元素[1,2]，刚好组成原数组，且没有更短的k满足条件

可行的实现思路 #

思路1：暴力验证法（直观易实现） #

对于每个可能的k（从1到n-1），验证是否整个数组都符合循环节的规则：遍历数组的每个位置i，检查arr[i]是否等于arr[i % k]。如果所有位置都满足，那这个k就是候选的最小循环长度（因为我们从最小的k开始遍历），直接返回即可；如果遍历完所有k < n都不满足，返回n。

代码示例（Python）：

def min_cycle_length(arr):
    n = len(arr)
    # 遍历所有可能的循环长度
    for k in range(1, n):
        valid = True
        for i in range(n):
            if arr[i] != arr[i % k]:
                valid = False
                break
        if valid:
            return k
    # 没有找到更短的循环长度，返回数组本身长度
    return n

思路2：利用KMP前缀函数（高效优化） #

暴力法的时间复杂度是O(n²)，对于大数组不够高效。可以用KMP算法中的前缀函数来优化，时间复杂度降到O(n)。

前缀函数pi[i]表示数组前i+1个元素中，最长的相等前缀和后缀的长度。利用这个性质，我们可以快速计算最小循环长度：

1. 计算数组的前缀函数数组pi
2. 计算d = n - pi[-1]（n是数组长度，pi[-1]是最后一个元素的前缀函数值）
3. 验证d是否符合循环节规则，符合则返回d，否则返回n

代码示例（Python）：

def compute_prefix_function(arr):
    n = len(arr)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]
        while j > 0 and arr[i] != arr[j]:
            j = pi[j-1]
        if arr[i] == arr[j]:
            j += 1
        pi[i] = j
    return pi

def min_cycle_length(arr):
    n = len(arr)
    if n == 0:
        return 0
    pi = compute_prefix_function(arr)
    d = n - pi[-1]
    # 验证d是否符合循环规则
    valid = True
    for i in range(n):
        if arr[i] != arr[i % d]:
            valid = False
            break
    return d if valid else n

这个方法能完美匹配你给出的所有示例，且效率更高。

关于你尝试的两种思路 #

1. Dijkstra算法 #

Dijkstra算法主要用于图结构中的最短路径查找，和数组循环长度的问题匹配度很低——这个问题本质是数组的模式匹配问题，而非图路径问题，用Dijkstra会绕远路且效率低下，建议放弃这个思路。

2. 快慢指针 #

快慢指针常用于链表环检测或数组重复元素查找，但要适配数组循环长度问题需要调整逻辑：比如把数组看作无限循环序列，检测是否存在k使得arr[i] = arr[i+k]对所有i成立。但这个思路实现起来比前缀函数方法复杂，且效率没有优势，不如直接用前缀函数方案。

内容的提问来源于stack exchange，提问作者Haxet