如何实现数组的旋转无关唯一编码？

要实现你需要的旋转不变且唯一的数组编码，这里有两种通用、可行的解决方案，完全适配任意长度的重复元素数组：

方案1：最小表示法编码 #

原理 #

生成数组的所有旋转版本，选取其中字典序最小的数组作为这个循环结构的唯一编码。所有旋转后的数组的最小表示必然相同，满足旋转不变性；而不同的循环数组，它们的最小表示肯定不一样，保证了编码的唯一性。

高效实现（O(n)时间复杂度） #

不用真的生成所有n个旋转版本，借助「字符串最小表示法」的思路就能快速找到最小版本：

1. 将原数组拼接成 arr + arr（例如 [1,3,2,3] 变成 [1,3,2,3,1,3,2,3]）
2. 在拼接后的数组中，找到长度为n的最小子数组，这就是原数组的最小表示

示例代码（Python）：

def min_representation(arr):
    n = len(arr)
    if n == 0:
        return []
    arr_double = arr + arr
    i, j = 0, 1
    k = 0
    while i < n and j < n and k < n:
        a = arr_double[i + k]
        b = arr_double[j + k]
        if a == b:
            k += 1
        else:
            if a > b:
                i += k + 1
            else:
                j += k + 1
            if i == j:
                j += 1
            k = 0
    start = min(i, j)
    return arr_double[start:start + n]

def encoded(arr):
    return tuple(min_representation(arr))  # 转成tuple方便作为哈希键或存储

验证示例：

a = [1, 3, 2, 3]
rotatedA = [3, 2, 3, 1]
print(encoded(a) == encoded(rotatedA))  # 输出True

方案2：循环哈希签名法 #

原理 #

用多项式滚动哈希计算数组的所有旋转版本的哈希值，然后取这些哈希的最小值（或最大值）作为编码。所有旋转版本的哈希集合一致，最小值也相同，满足旋转不变性；不同数组的哈希最小值几乎不会重复（用双哈希可进一步降低冲突概率）。

实现步骤 #

1. 选取大质数作为哈希的基数和模数，比如 base = 911382629，mod = 10**18 + 3
2. 计算原数组的多项式哈希值，以及基数的n次方模模数
3. 用滚动公式O(n)算出所有旋转版本的哈希值
4. 取最小的哈希值作为最终编码

示例代码（Python）：

def cyclic_hash(arr):
    n = len(arr)
    if n == 0:
        return 0
    base = 911382629
    mod = 10**18 + 3
    hash_val = 0
    base_n = 1
    for num in arr:
        hash_val = (hash_val * base + num) % mod
        base_n = (base_n * base) % mod
    min_hash = hash_val
    current_hash = hash_val
    for num in arr[:-1]:
        # 滚动计算旋转后的哈希值
        current_hash = ((current_hash - num * base_n) % mod) * base + num
        current_hash %= mod
        if current_hash < min_hash:
            min_hash = current_hash
    return min_hash

def encoded(arr):
    return cyclic_hash(arr)

注意事项 #

• 若担心哈希冲突，可以同时计算两种不同参数的哈希，返回(hash1, hash2)作为编码，冲突概率几乎为0
• 该方法时间复杂度O(n)，空间复杂度O(1)，适合处理大规模数组

关于你之前尝试的补充说明 #

• 「固定旋转至特定位置」的思路本质就是最小/最大表示法，之前未成功可能是没找到高效实现，或是没处理好重复元素的场景
• 「环形链表」无法直接解决编码问题，核心还是要提取循环结构的唯一特征（比如最小表示或哈希）
• 「最大值间距法」仅适配长度7的数组，是因为它依赖特定的位置关系，不具备通用性；上述两种方案适用于任意长度的数组

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