求高效算法：统计数组中的循环移位对数量

核心优化思路 #

暴力解法的问题在于要逐个生成每个数的所有循环移位，再两两比对确认是否为循环移位对，时间复杂度高达O(N²*M)（N是数组长度，M是数字平均位数），数据量一大必然超时。

优化的核心逻辑是：给同一循环移位组的所有数字分配一个唯一的规范标识，通过统计每个标识的出现次数，用组合数直接计算该组内的有效对数，彻底避免两两比对的冗余操作。

具体实现步骤 #

1. 生成数字的规范标识 #

对于每个数字，我们需要生成一个能代表其所属循环移位组的唯一key：

• 将数字转为固定长度的字符串（必须保留前导零，因为循环移位对要求两个数等长，比如5604是4位，其循环移位0456要以4位字符串处理，防止和3位的456混淆）。
• 生成该字符串的所有循环移位：可以通过将字符串拼接自身（如s = "5604"，拼接后为"56045604"），然后截取所有长度为原字符串长度的子串，这些子串就是全部循环移位形式。
• 从所有循环移位子串中选取最小值（或最大值，只要规则统一即可）作为该数字的规范标识。同一循环移位组的数字会生成完全相同的标识。

示例代码：

def get_canonical(num):
    s = str(num)
    n = len(s)
    doubled_str = s + s
    # 遍历所有长度为n的子串，取最小值作为规范标识
    return min(doubled_str[i:i+n] for i in range(n))

2. 统计标识出现次数 #

用哈希表（字典）遍历数组，记录每个规范标识的出现次数：

from collections import defaultdict

nums = [13, 5604, 31, 2, 13, 4560, 546, 654, 456]
count_map = defaultdict(int)

for num in nums:
    key = get_canonical(num)
    count_map[key] += 1

3. 计算总循环移位对数量 #

对于每个标识的出现次数k，满足0 ≤ i < j < len(nums)的有效对数是组合数k*(k-1)//2（从k个元素中选2个的组合数）。将所有标识对应的组合数相加，就是最终结果：

total_pairs = 0
for cnt in count_map.values():
    total_pairs += cnt * (cnt - 1) // 2

print(total_pairs)  # 输出5，与示例完全匹配

复杂度分析 #

• 时间复杂度：O(NM²)，其中N是数组长度，M是数字的平均位数。相比暴力解法的O(N²M)，当N较大时（比如1e4及以上），这个优化会带来数量级的性能提升。
• 空间复杂度：O(N*M)，主要用于存储哈希表中的规范标识，在合理范围内。

关键注意事项 #

• 必须保留数字的位数信息：不同长度的数字不可能是循环移位对，通过固定长度的字符串处理，它们的规范标识长度不同，自然不会被统计到同一组。
• 前导零的处理：循环移位产生的前导零要保留为字符串的一部分，比如5604的循环移位0456作为4位字符串处理，不会和3位的456混淆，因为两者的规范标识长度不同。

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