提问人：Szyszka947 提问时间：11/11/2023 更新时间：11/11/2023 访问量：49
为什么通过计数位然后用 x 取模来在 xn + 1 个数字中找到唯一数
Why finding unique number among xn + 1 numbers by counting bits and then modulo by x works
问：
我知道，如果我们给出的数组看起来像这样： ，其中每个数字都是重复的，除了数组中唯一的一个数字，那么我们可以：[7,6,7,6,5,7,6]x
- 将数字（它是二进制表示）一个写在另一个上面
- 然后我们可以计算 resuling 列中的位数
- 然后通过执行（从列计数）mod x，我们将获得数组中包含的唯一数的二进制表示。
i
此过程如下所示：
它有效。但它为什么有效？我无法理解。请解释。
答：
1赞
btilly
11/11/2023
#1
当你计算比特时，无论比特的顺序是什么，你都会得到相同的答案。因此，如果你对数字进行排序，qe 会得到 samw 答案。
但是当你对数字进行排序时，你会得到重复数字的“x”块。这意味着一个 0 的块加到 0，或者一个 1 的块是 0 mod 'x'。无论哪种方式，重复的数字都会消失，只留下唯一的数字。
评论
0赞
Szyszka947
11/11/2023
明白了。计数为（y 为 n，位置上有位的数字除外），因此这意味着我们在此位置的唯一编号为 0 位。如果计数是 ，那么在这个位置我们的数字将有 ..我明白了吗？xy0ixy + 11
1赞
btilly
11/13/2023
@Szyszka947 没错。
1赞
trincot
11/11/2023
#2
如果某个位（如第三个最低有效位）的唯一值为 0，那么我们知道该位的值在所有输入值上的总和必须是 x 的倍数，因为如果其中一个重复值设置为 1，那么我们已经有 x 个。如果它还设置为另一个重复值，那么我们有新的 x 集......每次得到的总数是 X 的倍数。因此，在这种情况下，该位模 x 的总和为 0。
在另一种情况下，如果该特定位的唯一数为 1，则总和将比 x 的倍数多 1（相同的推理）。因此，该位模 x 的总和为 1。
对于每个位位置，此原理的工作方式完全相同。
上一个：BST 输出差异 - 寻求解决
下一个：将整数从（纯）二进制转换为BCD
评论