14

给定一个数组，其中每个数字的出现次数为奇数，但出现次数为偶数的数字除外。找到偶数出现的数字。

例如

1, 1, 2, 3, 1, 2, 5, 3, 3

输出应该是：

2

以下是约束：

  1. 数字不在范围内。
  2. 就地进行。
  3. 所需的时间复杂度为 O(N)。
  4. 数组可能包含负数。
  5. 数组未排序。

由于上述限制，我所有的想法都失败了：基于比较的排序、计数排序、BST、散列、蛮力。

我很想知道：XORing 会在这里工作吗？如果是，如何？

4

3 回答 3

4

这个问题已经困扰了我好几天的地铁行程。这是我的想法。

如果 A. Webb 是对的，并且这个问题来自采访或者是某种学术问题，我们应该考虑一下我们所做的（错误的）假设，并可能尝试探索一些简单的案例。

想到的两个极端子问题如下：

  • 该数组包含两个值：一个重复偶数次，另一个重复奇数次。
  • 该数组包含n-1 个不同的值：所有值都出现一次，除了一个值出现两次。

也许我们应该根据不同值数量的复杂性来拆分案例。

如果我们假设不同值的数量为 O(1)，则每个数组将具有m不同的值，且与m无关n。在这种情况下，我们可以遍历原始数组擦除并计算每个值的出现次数。在这个例子中，它会给

1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase
-> Stop because 2 was found an even number of times.

这将解决复杂度为的第一个极端示例O(mn)，其计算结果为O(n)。

更好的是：如果不同值的数量是O(1)，我们可以在哈希映射中计算值的出现次数，在读取整个数组后遍历它们并返回出现偶数次的值。这仍然被认为是O(1)记忆。

第二种极端情况是在数组中找到唯一重复的值。这在 中似乎是不可能的O(n)，但在某些特殊情况下我们可以做到：如果数组中有n元素并且内部的值是{1, n-1}+ 重复值（或某些变体，例如x 和 y 之间的所有数字）。在这种情况下，我们将所有值相加，从总和中减去n(n-1)/2，然后检索重复的值。

在我看来，用数组内的随机值解决第二个极端情况，或者在常量内存和时间中m不是常量 on的一般情况似乎是不可能的。nO(n)

额外说明：这里，XORing 不起作用，因为我们想要的数字出现偶数次，而其他数字出现奇数次。如果问题是“给出出现奇数次的数字，所有其他数字出现偶数次”，我们可以对所有值进行异或运算并在最后找到奇数。

我们可以尝试使用这种逻辑寻找一种方法：我们需要一个类似函数的东西，对一个数字应用奇数次将产生 0，而偶数次将产生恒等式。不要认为这是可能的。

于 2012-10-24T22:31:51.760 回答
2

介绍

这是一个可能的解决方案。这是相当做作且不实用的，但是问题也是如此。如果我的分析中有漏洞，我将不胜感激。如果这是一个“官方”解决方案的作业或挑战问题，我也很想看看原始海报是否仍然存在，因为距离被问到已经过去了一个多月。

首先，我们需要充实问题的一些不明确的细节。所需的时间复杂度是O(N)，但什么是N？大多数评论员似乎都在假设N数组中的元素数量。如果数组中的数字具有固定的最大大小，这将是可以的，在这种情况下，Michael G 的基数排序解决方案将解决问题。但是，在原始发帖人没有澄清的情况下，我将约束 #1 解释为不需要固定最大位数。因此，如果n（小写）是数组中的元素个数，以及元素m的平均长度，那么要应对的总输入大小为mn。求解时间的下界是O(mn)因为这是验证解决方案所需的输入的通读时间。因此，我们想要一个与总输入大小成线性关系的解决方案N = nm。

例如，我们可能有n = m，即平均长度的sqrt(N)元素。sqrt(N)比较排序需要O( log(N) sqrt(N) ) < O(N)运算，但这不是胜利，因为运算本身平均需要O(m) = O(sqrt(N))时间，所以我们回到O( N log(N) ).

O(mn) = O(N)此外，如果m是最大长度而不是平均长度，则将采用基数排序。如果假设数字落在某个有界范围内，则最大和平均长度将处于相同的顺序，但如果不是这样，我们可能会有一个小百分比的数字大且可变，而大百分比的数字数字少. 例如，10% 的数字可能是 lengthm^1.1和 90% 的 length m*(1-10%*m^0.1)/90%。平均长度是m，但最大长度m^1.1是 ，所以基数排序是O(m^1.1 n) > O(N)。

免得有人担心我对问题定义的改动太大，我的目标仍然是描述一种时间复杂度与元素数量成线性关系的算法，即O(n). 但是，我还需要对每个元素的长度执行线性时间复杂度的操作，因此这些操作在所有元素上平均为O(m). 这些操作将是计算元素哈希函数和比较所需的乘法和加法。如果这个解决方案确实解决了 中的问题O(N) = O(nm)，那么这应该是最佳复杂度，因为验证答案需要相同的时间。

问题定义中省略的另一个细节是是否允许我们在处理数据时销毁数据。为了简单起见，我将这样做，但我认为如果格外小心，它可以避免。

可能的解决方案

首先，可能存在负数的约束是空的。通过一次数据，我们将记录最小元素z和元素数量n。在第二次通过时，我们将添加(3-z)到每个元素，所以现在最小的元素是 3。（请注意，恒定数量的数字可能会因此溢出，因此我们应该首先对数据进行恒定数量的额外遍历以进行测试这些是解决方案。）一旦我们有了解决方案，我们只需简单地减去(3-z)即可将其恢复为原始形式。现在我们可以使用三个特殊的标记值0、1和2，它们本身不是元素。

步骤1

使用中位数选择算法来确定数组的第 90 个百分位元素 ，p并将数组A划分为两个集合，S其中T元素大于和小于。这需要步骤（平均总步骤）时间。匹配的元素可以放在或中，但为了简单起见，遍历数组一次并通过将其替换为 来测试和消除它。Set最初跨越索引，其中是 about of和 setS10% of npTpO(n)O(m)O(N)pSTp0S0..ss10%nT跨越其余 90% 的索引s+1..n。

第2步

现在我们要循环遍历i in 0..s每个元素e_i，我们要计算一个散列函数h(e_i)到s+1..n. 我们将使用通用散列来获得均匀分布。因此，我们的散列函数将进行乘法和加法，并在每个元素的长度上花费线性时间。

我们将对碰撞使用修改后的线性探测策略：

  1. h(e_i)T被（意思是A[ h(e_i) ] < p但不是标记1或）的成员占据，2或者是0。这是一个哈希表未命中。e_i通过从插槽i和交换元素来插入h(e_i)。

  2. h(e_i)S 被（意思A[ h(e_i) ] > p）或标记1或的成员占据2。这是一个哈希表冲突。进行线性探测，直到遇到 or 的副本或e_i成员。T0

    • 如果是 的成员T，这又是一个哈希表未命中，因此e_i通过(1.)交换到 slot 来插入i。

    • 如果 的重复e_i，这是一个哈希表命中。检查下一个元素。如果那个元素是1or 2，我们已经不止一次看到e_i了，将1s 更改为2s ，反之亦然，以跟踪其奇偶校验的变化。如果下一个元素不是1or 2，那么我们之前只见过e_i一次。我们希望将 a 存储2到下一个元素中，以表明我们现在已经看到e_i了偶数次。我们寻找下一个“空”槽，也就是一个被T我们移动到槽的成员占用的槽i，或者一个 0，然后将元素向上移动以h(e_i)+1向下索引，这样我们旁边就有空间h(e_i)来存储我们的奇偶校验信息. 注意我们不需要存储e_i本身又一次，所以我们没有用完额外的空间。

所以基本上我们有一个功能哈希表，其中槽数是我们希望哈希的元素的 9 倍。一旦我们开始获得命中，我们也开始存储奇偶校验信息，所以我们最终可能只有 4.5 倍的插槽数，仍然是一个非常低的负载因子。有几种碰撞策略可以在这里工作，但由于我们的负载因子很低，平均碰撞次数也应该很低，线性探测应该以适当的时间复杂度平均解决它们。

第 3 步

0..s一旦我们完成了into的元素散列s+1..n，我们就遍历s+1..n. 如果我们找到 S 的一个元素后跟 a 2，那是我们的目标元素，我们就完成了。任何元素后跟指示e的另一个元素只遇到一次并且可以归零。同样，后面是我们看到奇数次的手段，我们可以将和 标记归零。SSee1ee1

根据需要冲洗并重复

如果我们还没有找到我们的目标元素，我们重复这个过程。我们的第 90 个百分位分区会将 10% 的n剩余最大元素移动到开头，A并将剩余元素（包括空0标记槽）移动到末尾。我们像以前一样继续进行散列。我们最多必须这样做 10 次，因为我们n每次处理 10%。

结论分析

通过中位数算法进行分区的时间复杂度为O(N)，我们做了 10 次，仍然是O(N)。O(1)由于哈希表负载较低，并且总共O(n)执行了哈希操作（10 次重复中的每一次，大约为 n 的 10%），因此每个哈希操作平均进行。每个元素都有一个为它们计算的散列函数，时间复杂度与它们的长度成线性关系，因此平均而言是所有元素。因此，总体上的散列操作是。所以，如果我已经正确分析了这一点，那么总的来说这个算法是. （如果加法、乘法、比较和交换操作被假定为相对于输入的恒定时间，也是如此。）nO(m)O(mn) = O(N)O(N)+O(N)=O(N)O(n)

请注意，该算法没有利用问题定义的特殊性质，即只有一个元素出现偶数次。我们没有利用问题定义的这种特殊性质，这使得存在更好（更聪明）算法的可能性成为可能，但最终也必须是 O(N)。

于 2012-10-26T17:23:57.567 回答
0

请参阅以下文章：在 O(n) 时间内运行并在原地排序的排序算法，假设最大位数是恒定的，我们可以在 O(n) 时间内对数组进行原地排序。

之后就是计算每个数字的出现次数，平均需要 n/2 时间才能找到出现次数为偶数的数字。

于 2012-10-22T10:21:58.160 回答