有序正整数序列中满足X XNOR Y = -1的数对高效查找算法优化咨询

嘿，这个问题其实可以通过拆解位运算的本质来大幅优化，根本不用暴力的双重循环！先帮你理清楚核心逻辑：

关键转化：从位运算到重复元素统计 #

首先要搞明白X XNOR Y = -1到底意味着什么。在Python中，整数是以补码形式存储的，-1的二进制表示是无限个连续的1（因为Python支持任意精度的大整数）。

而同或（XNOR）运算的规则是：两个二进制位相同则结果为1，不同则为0。要让整个运算结果为-1（全1），就要求X和Y的每一位二进制位都完全相同——换句话说，X必须等于Y！

这一下就把问题从复杂的位运算判断，转化成了统计升序序列中重复元素的配对数量，以及输出所有相同元素的配对。

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

因为序列是升序排列的，相同元素必然是连续出现的。我们可以通过一次遍历序列，统计每个连续相同元素的出现次数，然后计算该元素的配对数（从k个元素中选2个的组合数：k*(k-1)//2），同时输出所有配对。

完整实现代码（输出所有配对+统计总数） #

def find_xnor_pairs(seq):
    if not seq:
        print("匹配总数为0")
        return 0
    
    total_pairs = 0
    current_num = seq[0]
    count = 1
    
    # 遍历序列从第二个元素开始
    for num in seq[1:]:
        if num == current_num:
            count += 1
        else:
            # 计算当前连续元素的配对数并输出
            pairs = count * (count - 1) // 2
            total_pairs += pairs
            for _ in range(pairs):
                print(f"X={current_num}, Y={current_num}")
            # 更新当前元素和计数
            current_num = num
            count = 1
    
    # 处理最后一组连续元素
    pairs = count * (count - 1) // 2
    total_pairs += pairs
    for _ in range(pairs):
        print(f"X={current_num}, Y={current_num}")
    
    print(f"匹配总数为{total_pairs}")
    return total_pairs

# 测试示例输入
test_seq = [1, 2, 3, 3, 4, 4, 4, 10, 10, 10]
find_xnor_pairs(test_seq)

运行这段代码会得到和示例完全一致的输出，而且时间复杂度是O(n)，比双重循环的O(n²)高效得多，尤其是当序列长度很大时，优势会非常明显。

简化版本（仅统计配对总数） #

如果不需要输出具体的配对，只需要统计总数，我们可以用collections.Counter来快速统计元素出现次数，再计算总和：

from collections import Counter

def count_xnor_pairs(seq):
    num_counter = Counter(seq)
    total = sum(k * (k - 1) // 2 for k in num_counter.values())
    print(f"匹配总数为{total}")
    return total

# 测试
count_xnor_pairs(test_seq)

这个版本的时间复杂度同样是O(n)，代码更简洁。

为什么这个方法正确？ #

再强调一次核心逻辑：

• 当且仅当X和Y的每一位二进制位都相同时，X XNOR Y的结果才会是全1（也就是-1）
• 而每一位都相同的两个整数，必然是相等的

所以问题等价于找序列中所有相等元素的配对，这也是我们能把复杂度从O(n²)降到O(n)的关键原因。

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