处理n中的m个事件

对于计算sum mod n的每一个求和操作,您执行64个求和,每一位一个,对于结果中应设置的每一位,此计算返回m,对于不应设置的每一位,返回0。

例子:
n=3,m=2。列表=[5 11 5 2 11 5 2 11]

              5  11   5   2  11   5   2  11
sum of bit 0: 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1 = 6   6 % 3 = 0
sum of bit 1: 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 = 5   5 % 3 = 2
sum of bit 2: 1 + 0 + 1 + 0 + 0 + 1 + 0 + 0 = 3   3 % 3 = 0
sum of bit 3: 0 + 1 + 0 + 0 + 1 + 0 + 0 + 1 = 3   3 % 3 = 0

所以只设置了位1,这意味着结果是2。

优化实施:
(对实际问题也有用的技巧和注意事项)
值得注意的是,在对数组进行迭代时,执行速度在一定程度上会受到内存访问的限制,如果需要对每个元素执行多个操作,那么一次对一个元素执行所有操作通常是最快的,因此处理器只需要从内存加载一次每个元素。 Interesting blog post on memory and cache.

可以在一个整数中求和多个位,而不是应用64个不同的位掩码来获得每个位,例如,一个只能使用4个位掩码来提取16个位,每个位之间有3个位的空间,只要不发生溢出,正常的加法操作就可以像处理16个4位整数一样工作,因此这种方法适用于15个数字。以这种方式处理15个数字后,结果必须添加到能够容纳更大整数的存储器中(可以是8个64位整数,每个8位整数都可以容纳8个8位整数,当然,它们必须依次清空为更大的整数等)。
结果是,不需要对每个值执行64位掩码、63位移位和64位加法,只需要执行4位掩码、3位移位和4位加法,每15个值加8位掩码、4位移位和8位加法,每255个值加16位掩码、8位移位和16位加法等。

可视化:
(使用16位整数求和4x4位整数)

1000 1000 1000 1000 +
1000 0000 0000 1000 +
0000 0000 0000 1000 +
1000 1000 0000 0000 +
1000 0000 1000 0000 +
0000 0000 1000 1000 =
0010 0100 1100 0010

结果是相同的,无论您认为这是4列4位整数还是1列16位整数,这只是正确的,只要4位整数不溢出。

编辑) 好吧,这个方法不像我最初想象的那么好。电子商务的解决方案简单得多,适用于N=4、M=2等情况。

我们可以将xor方法泛化为使用任意 米 和 n . 我们首先要选一个基地 乙 这样 GCD(n,b)=b 和 GCD(M,B)和lt;B . 如奇 n /甚至 米 对满足这一点对于基2,标准的二进制XOR适用于这些对。

首先我们定义 (a^ ^ n) 意味着 (a^ a^…^ a) 对于 氮甲 's,具有基本的通用异或 乙 . 例如,使用标准二进制XOR, a^ ^ 2=0 .

我们需要定义我们的通用XOR。我们想要的性质基本上与加法(交换性、结合性)相同,我们需要 a^ ^ b=0 . 显而易见的解决办法是 (x^ y)=(x+y)%b 对于基数中的每个数字 乙 表示法(让自己相信这是可行的,并且与基2的二进制XOR相同)。然后,我们简单地把它应用到序列中的所有数字,最后得到 结果=s^^(m%b) ,其中s是特殊编号。
最后,我们需要恢复我们的“异化”基础 乙 数字到预期的数字。我们可以简单地计算 i ^(m%b) 对于 I=0…B-1 ,然后查找我们拥有的价值 S 中的每个数字 结果 .

这个算法是O(N)。对于列表中的每个数字,我们都有一个常量的操作要做,因为我们最多有64位数字。对于大B来说,最坏的情况是在末尾进行还原。我们可以通过计算在常量空间中完成最后一步。 i ^(m%b) 为了所有 我 对于每个数字(同样,我们有一个恒定的数字数)。

例子:

n =3, 米 = 2。列表= [5 11 5 2 11 5 2 11]

首先我们选择一个基地 乙 . 显然我们必须选择3垒。

供参考的XOR表:

  0|1|2
0|0|1|2
1|1|2|0
2|2|0|1

计算:

  5     11      5      2     11      5      2     11
0^0=0. 0^1=1. 1^0=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0.
0^1=1. 1^0=1. 1^1=2. 2^0=2. 2^0=2. 2^1=0. 0^0=0. 0^0=0.
0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1. 1^2=0. 0^2=2. 2^2=1.

m % b = 2.

因此,S ^^2=[001]。我们为每个数字i生成一个i^2的表,然后进行反向查找。

   i | 0 | 1 | 2 |
i^^2 | 0 | 2 | 1 |

0 -> 0
0 -> 0
1 -> 2

最后,我们将结果转换回二进制/十进制。〔002〕=2。

最简单的情况可以更一般,可以使用与奇数相同的方法 米 偶数 n .

这里有一个与电子商务运行时间相同的解决方案(我认为它实际上是O(n log n)),但真正使用的是O(1)字的内存。它假定m不是n的倍数。它还假定两个助手函数严格计算参数上下的元素数。

int divider = 0;

for (int i = 63; i >= 0; i--) {
  divider |= 1 << i;
  int a = countAbove(divider);
  int b = countBelow(divider);
  if (a % n == 0 && b % n == 0) return divider;
  else if (a % n == 0) divider ^= 1 << i;
}

• 如果在0到(n/n)+1的整数集上有一对一的散列,那么可以通过n个迭代+n/n个迭代和n个内存使用率来求解它。但是没有一对一的映射

• 如果对内存没有约束,那么它必须是常量,您可以定义一个数组,该数组的长度域的大小,这样您就可以在2n中用常量的大量内存使用来解决这个问题。对于n中的每一个x,只需添加到bigarry[x]中,然后通过bigarry循环查找m。它很糟糕,不可实现,但满足要求,而且大多数面试问题都被认为是实验。

如果对列表进行排序,那么这就变得非常简单,因为您只需要依次检查每个批次,看看它是否是长度m。

如果列表没有排序,那么我认为使用O(1)附加内存是不可能的。

我相信你不能只用0(1)个额外的空间。

这是我的理由:你被给予:

• 米
• n
• XY1 XY2…XYN

由于x_i值中存在重复项,我们将u定义为一组唯一值。u中的所有元素都出现n次,其中一个元素在x_i系列中出现m次。让我们将不太常见的元素标记为u_0,而u_1将设置为u-u_0。

我们是所有x的总和,可以写成:

sum(x_i) = n * sum(U_1) + m * u_0 = n * sum(U) + (m - n) * u_0

解决这个问题就相当于在一个序列中找到唯一元素的和,而在O(1)额外的空间中不能这样做,因为您需要一个带有链接元素的数组或哈希表-该空间实际上是O(n)

解的过程类似于求k阶统计量的过程。

by dividing the sequence into 2 sub-seqs
(calculate the size of sub-seqs during the procedure)
while (sizeof(sub-seq) mod n != 0)
  do the same porcess on this sub-seq(dividing)

o(n)查找k阶统计量等操作。