我在接受采访时被问到这个问题.
鉴于此,有3n + 1个数字.这些数字中的n个出现在三元组中,只有1个出现在单个时间内.我们如何在线性时间内找到唯一的数字,即O(n)？这些数字没有排序.
请注意,如果有2n + 1个数字,其中n个成对出现,我们可以对所有数字进行异或,以找到唯一的数字.面试官告诉我,这可以通过比特操纵来完成.
algorithm
algorithm ×1