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

Question

这是问题所在（简而言之）：

We're given an array with N natural numbers and a val K. We need to find the number in the array which appears a single time knowing that any other number in my array appears exacly K times.

We need to find that number.

限制和规范

200.000 <= N <= 300.000
2 <= K <= 15
Any number in my array is a natural number between 0 ... 2^64-1

内存和执行时间限制：

Memory: 0.5 Mb
Time: 0.6 seconds

示例：

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

可能是我理解错了，不过这里有一个解决方法。

使用就地排序算法对数组进行排序。因为它是就地的，所以你不需要比初始数组更多的space。这比地图 space 更有效。
遍历数组，如果找到一个没有重复的数字，那就是你的数字。

您甚至可以通过迭代每个第 K 个元素并查看前一个数字是否不同来优化步骤 2。（当目标数字是集合中最大或最小数字时，您仍然必须处理特殊情况）

Answer 2

我假设输入已读取但太大而无法存储。

因此，当您阅读它时，数一数为 64 位中的每一位设置 N 位的次数。然后取每个计数的余数 mod K，对于每个位位置，它是零或 1，给出该位位置的值。

如果您不介意编写大量繁琐的代码，您可以编写六个不同的布尔 mod 线性计数例程，并且 select 其中一个基于 K 的最低质因数： 2、3、5、7、11 或 13。

这避免了 64 位上的所有循环，对于 2 应该快 64 倍以上，对于最坏情况 13 可能仍然快 8 倍以上。

例如布尔计数 mod 3 可以通过以下方式完成：在循环之前 a=b=0 然后对于每个输入 x

z = a | b;
a ^= x & ~b;
b ^= x & z;

然后最后结果在a

对于 5 你可以从 a=b=c=0 开始并使用：

b ^= x & a;
a ^= x & ~c;
c ^= x & ~(a|b);

7:

a ^= x & ~(c & b);
z = x & ~a;
c ^= b & z;
b ^= z;

玩得开心 11 和 13。在所有情况下，最终答案都在 a 中，没有额外的完成工作。缺少错误或输入错误，最后 b、c 和（如果需要）d 都将为零，因此这是一个简单的完整性检查。

Answer 3

您可以在快速线性时间内执行此操作，并且额外的字节数少于 100 space。

如果 K 是偶数，则只需将所有元素异或即可。

想想它是如何工作的——考虑异或运算的一种方法是它把每一位都看作一个单独的数字。它将它们加在一起并产生结果 mod 2。任何乘以偶数的结果都是 0 mod 2，因此只有在出现一次的数字中设置的位保持设置。

如果 K 不是偶数，那么您可以做同样的工作，但是 mod 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;

加分项：如果您愿意，可以通过位并行添加来优化此解决方案（JSF 在这个方向上的回答点），但是对于您需要的任何东西，这可能都不是必需的。您可以使用 5 个 64 位整数来表示每个计数器的低 5 位。在将它们扩展到 bitvals 数组之前，这些计数器最多可以累积 31 个输入值。累积每个单词将如下所示：

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

Answer 4

首先对数组进行排序，然后遍历它以获得答案。这是逻辑，唯一元素可以在任何位置标记为 0, K, 2K, 3K, .., N-1

#include <iostream>
#include <algorithm>

using namespace std;

unsigned long long uniqueNumber(vector<unsigned long long> &arr, int K) {
    sort(arr.begin(), arr.end());
    int i = 0;
    for(i = K-1;i < arr.size();i += K) {
        if(arr[i] != arr[i-K+1])
            return arr[i-K+1];
    }
    return arr[i-K+1];
}

int main()
{
    vector<unsigned long long> A{1, 3, 5, 7, 5, 1, 3, 1, 5, 3};
    cout<<uniqueNumber(A, 3)<<endl;
    return 0;
}

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

Need to find an unique number in an array

c++

algorithm

implementation