需要在数组中找到唯一的数字

Question

这是问题(简而言之):

我们给出了一个具有N个自然数和一个val K的数组.我们需要找到数组中的数字,这个数字一次出现就知道我的数组中的任何其他数字都出现了K次.

我们需要找到这个数字.

限制和规格

200.000 <= N <= 300.000
2 <= K <= 15
我的数组中的任何数字都是0 ... 2 ^ 64-1之间的自然数

内存和执行时间限制:

记忆:0.5 Mb
时间:0.6秒

例:

Type:

N K
<array vals>

10 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维度的数组!

你们能给我一个想法吗？

Answer 1

您可以在快速线性时间内完成此操作,并且额外空间少于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; i<N; ++i)
{
    uint64_t val=data[i];
    for(int bit=0; bit<64; ++bit)
    {
        if (val & (((uint64_t)1)<<bit))
            bitvals[bit]+=1;
    }
}

//only the bits in the number that occurs once are non-zero mod K
//make that number
uint64_t ret=0;
for(int bit=0; bit<64; ++bit)
{
    if (bitvals[bit]%K)
        ret |= ((uint64_t)1)<<bit;
}
return ret;    

EXTRA CREDIT:如果你愿意,这个解决方案可以通过位并行添加进行优化(JSF在这个方向上的答案点),但这可能不是你需要它的必要条件.您可以使用5个64位整数来表示每个计数器的低5位.在将这些计数器扩展为位数数组之前,这些计数器最多可以累积31个输入值.累积每个单词看起来像这样:

   for (int i=0;i<5; i++)
   {
      uint64_t carry = parcounters[i]&val;
      parcounters[i]^=val;
      val=carry;
   }