这是问题(简而言之):
我们给出了一个具有N个自然数和一个val K的数组.我们需要找到数组中的数字,这个数字一次出现就知道我的数组中的任何其他数字都出现了K次.
我们需要找到这个数字.
限制和规格
200.000 <= N <= 300.000
2 <= K <= 15
我的数组中的任何数字都是0 ... 2 ^ 64-1之间的自然数
内存和执行时间限制:
记忆:0.5 Mb
时间:0.6秒
例:
Type: N K10 3 1 3 5 7 5 1 3 1 5 3
而已.我的主要问题是如何在我的数组(0 ... 2^64-1
)中处理如此大的数字.
我的想法听起来像是这样(假设数字来自0 to 9
):
- >我计算我的数组中每个数字(数字)的出现次数,并将其标记为(计算后的数字).
- >我从0迭代到9并且如果计算了数字(=我的数组中有这个数字)并且该数字的出现与K不同,我解决了问题.
但同样,我的数字来自0 to 2^64-1
,我不能声明一个2 ^ 64维度的数组!
你们能给我一个想法吗?
您可以在快速线性时间内完成此操作,并且额外空间少于100个字节.
如果K是偶数,那么只需将所有元素混合在一起就可以了.
想想它是如何工作的 - 考虑xor操作的一种方法是它将每个位视为一个单独的数字.它增加了它们放在一起,产生的结果MOD 2.任何乘以偶数为0模2,所以只有在出现一次保持置数量中设置的位.
如果K不是偶数,那么你可以做同样的工作,但是修改K(或K因子 - 3或5)而不是mod 2.
鉴于:
int K,N; //input values uint64_t data[N]; //array of numbers
代码如下所示:
//initialize a counter for each bit in the result int bitvals[64]; for (int bit=0; bit<64; ++bit) { bitvals[bit]=0; } //count the number of times each bit occurs in the array for(int i=0; iEXTRA CREDIT:如果你愿意,这个解决方案可以通过位并行添加进行优化(JSF在这个方向上的答案点),但这可能不是你需要它的必要条件.您可以使用5个64位整数来表示每个计数器的低5位.在将这些计数器扩展为位数数组之前,这些计数器最多可以累积31个输入值.累积每个单词看起来像这样:
for (int i=0;i<5; i++) { uint64_t carry = parcounters[i]&val; parcounters[i]^=val; val=carry; }