你有一个数组,其中每个数字重复奇数次(但超过单次出现).恰好一个数字出现一次.你怎么找到只出现一次的号码？
e.g.: {1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3}
答案是9.
我正在考虑使用哈希表,然后只计算计数为1的元素.这似乎微不足道,我没有使用其他元素重复奇数次的事实.有没有更好的方法.
描述
给定一个大小数组,(n*k+b)其中n个元素出现k次,一个元素出现b次,换句话说,有n+1不同的元素.鉴于0 < b < k找到b次元素.
我的尝试解决方案
显而易见的解决方案是使用散列,但如果数字非常大,则不起作用.复杂性是O(n)
使用map存储每个元素的频率,然后遍历map以找到b次出现的元素.由于Map的实现为高度平衡树,复杂性将是O(nlogn).
我的两个解决方案都被接受了,但是面试官想要一个线性解决方案,而不使用散列和暗示他给出的树的高度在你存储频率的树中保持不变,但我还没有找到正确的解决方案.
我想知道如何在没有散列的线性时间内解决这个问题？
编辑:
样品:
输入: n=2 b=2 k=3
Aarray: 2 2 2 3 3 3 1 1
输出: 1
我在接受采访时被问到这个问题.
鉴于此,有3n + 1个数字.这些数字中的n个出现在三元组中,只有1个出现在单个时间内.我们如何在线性时间内找到唯一的数字,即O(n)？这些数字没有排序.
请注意,如果有2n + 1个数字,其中n个成对出现,我们可以对所有数字进行异或,以找到唯一的数字.面试官告诉我,这可以通过比特操纵来完成.