查找数组中互为旋转关系的元素对的算法优化问题咨询

核心优化思路 #

互为旋转的字符串一定可以映射到同一个唯一基准标识，我们通过哈希表将所有相同基准标识的数字分到同一组，同组内的数字两两配对就是所需结果，无需两层遍历数组，可大幅降低时间复杂度。

具体实现步骤 #

• 前置粗分组（可选优化）：将所有数字转为字符串后，先按长度分组，不同长度的字符串不可能互为旋转，无需进入后续计算
• 生成基准标识：对每组内的每个字符串，生成它的所有旋转串，取字典序最小的串作为该字符串的唯一基准键；如果要进一步优化基准键生成效率，可以使用字符串最小表示法，将生成基准键的时间从O(k²)降到O(k)
• 哈希分组：将数字按基准键存入哈希表对应的列表中
• 生成结果：遍历哈希表所有分组，若组内元素数量≥2，生成组内所有两两不重复的元素对即可

复杂度分析 #

优化后整体时间复杂度为O(nk)（使用最小表示法生成基准键的场景），其中n为数组长度，k为字符串平均长度，远优于原方案的O(n²k)，在n较大的场景下性能提升尤其明显。

参考实现伪代码 #

def find_rotation_pairs(arr):
    # 按字符串长度粗分组
    len_group = {}
    for num in arr:
        s = str(num)
        l = len(s)
        if l not in len_group:
            len_group[l] = []
        len_group[l].append(s)
    
    res = []
    for group in len_group.values():
        hash_map = {}
        for s in group:
            # 生成最小旋转串作为基准键，此处可以替换为最小表示法实现优化
            min_rot = min(s[i:] + s[:i] for i in range(len(s)))
            if min_rot not in hash_map:
                hash_map[min_rot] = []
            hash_map[min_rot].append(int(s))
        # 生成配对
        for nums in hash_map.values():
            m = len(nums)
            for i in range(m):
                for j in range(i+1, m):
                    res.append((nums[i], nums[j]))
    return res

边界说明 #

如果不允许相同数字的配对（比如数组中存在两个13的场景），可以提前对数组做去重处理即可。

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