logo标签列表

我该如何在O(n)时间内在已排序的数组中找到一个出现奇数次的数字？

calgorithmasymptotic-complexity
40

我有一个问题，思考了很多次却没有想出答案...所以在这里发布这个问题。也许我能得到别人的观点，尝试让它起作用...

问题是：给定一个排序好的数组，其中包含一个出现奇数次数的值和其他出现偶数次数的值。我们需要在log n时间内找到解决方案。

在O（n）时间内找到解决方案很容易，但是在log n时间内执行看起来相当棘手。

4
这个数组里的数字是连续的整数吗？目前为止似乎没有比((log N)^2)更好的答案，但也没有直接利用数组已排序的特性。 - Pete Kirkham
3
酷毛病！他们在哪里布置这样好的问题作业？ :) - Kris
1
@AGeek 请在您的作业接受期结束后发布解决方案。谢谢。 - Dave O.
1
@Bragboy 如果所有问题都像这个一样难回答，那将会很困难^^。 - Dave O.
1
@joe snyder和其他任何人：解决O(log(n)^2)运行问题是微不足道的。甚至运行在O(log(n))的解决方案尚未被发现(!) - 或者证明不存在这样的算法。 - Dave O.
显示剩余10条评论
14个回答
30
定理: 对于这个问题的每个确定性算法，在最坏情况下需要探查Ω(log2n)内存位置。 证明（完全以更正式的风格重写）:
设k > 0为一个奇数，n = k2。我们描述一个对手可以强制（log2(k+1))2=Ω(log2n)探针的敌手。
我们将相同元素的最大子序列称为组。 对手的可能输入包括k个长度为k的段x1x2… xk。 对于每个段xj，存在一个整数bj ∈ [0，k]，使得xj由j-1的bj次复制和k-bj次j的复制组成。 每个组最多与两个段重叠，每个段最多与两个组重叠。
Group boundaries
|   |     |   |   |
 0 0 1 1 1 2 2 3 3
|     |     |     |
Segment boundaries

无论何时增加了两个，我们都默认有一个双重边界。

Group boundaries
|     ||       |   |
 0 0 0  2 2 2 2 3 3
声明: 第j个组的边界位置（1 ≤ j ≤ k）由xj这一线段唯一确定。 证明: 它就在((j - 1)k + bj)th个内存位置之后，并且xj唯一确定了bj。//
我们说算法观察到第j个组的边界，当它对xj的探测结果唯一地确定xj时。根据惯例，输入的开头和结尾总是被观测到的。算法有可能在不观测到边界的情况下唯一确定某个组的边界位置。
Group boundaries
|   X   |   |     |
 0 0 ? 1 2 2 3 3 3
|     |     |     |
Segment boundaries

给定只有 0 0 ?，算法不能确定 ? 是 0 还是 1。但在上下文中，? 必须为 1，否则将会有三个奇数分组，并且可以推断出 X 处的分组边界。这些推断可能对敌手造成问题，但事实证明，只有在相关分组边界变得“无关紧要”时才能进行这些推断。

声明: 在算法执行过程中的任何时间点，考虑它观察到的分组边界集合。恰好有一个连续的偶数距离的分组边界对，并且奇数分组位于它们之间。

证明: 每个其他连续对仅限于偶数分组。//

定义由特殊连续对限定的奇数长度子序列为相关子序列。

声明: 在相关子序列内部的任何分组边界都不能被唯一确定。如果存在至少一个此类边界，则奇数分组的标识不是唯一确定的。

证明: 不失一般性地假设已经探测了不在相关子序列中的每个存储位置，并且包含在相关子序列中的每个分段恰好有一个尚未被探测的位置。假设第 j 个分组边界（称其为 B）位于相关子序列的内部。根据假设，对 xj 的探测将 B 的位置确定为两个相邻的可能性。我们将距离左侧观察到的边界奇数距离的那个称为奇数左侧，另一个称为奇数右侧。对于两种可能性，我们从左到右工作，并固定每个剩余内部分组边界的位置，以便其左侧的分组是偶数的。（我们之所以能够这样做，是因为它们都有两个相邻的可能性。）如果 B 在奇数左侧，则其左侧的分组是唯一的奇数分组。如果 B 在奇数右侧，则相关子序列中的最后一个分组是唯一的奇数分组。两者都是有效输入，因此算法既没有唯一地确定 B 的位置，也没有唯一确定奇数分组。//

示例：

Observed group boundaries; relevant subsequence marked by […]
[             ]   |
 0 0 Y 1 1 Z 2 3 3
|     |     |     |
Segment boundaries

Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1
由于这一声明的影响，算法无论如何运作都必须将相关子序列缩小到一个组。因此根据定义，它必须观察一些组边界。攻击者现在的任务是尽可能保持开放的可能性。在算法执行的任何时刻，攻击者在相关子序列之外的每个内存位置上内部承诺于一个可能性。在开始时，相关子序列是整个输入，因此没有初始承诺。每当算法探测到xj的未承诺位置时，攻击者必须承诺其中的一个值：j-1或j。如果它能够避免让第j个边界被观察到，它会选择留下至少一半的剩余可能性（相对于观察）。否则，它会选择保持相关区间中至少一半的组，并为其他组承诺价值。通过这种方式，攻击者迫使算法观察至少log2(k+1)个组边界，在观察第j个组边界时，算法被迫进行至少log2(k+1)次探测。 扩展： 这个结果可以直接推广到随机算法中，通过随机化输入，在从算法的角度来看，将“至少减半”替换为“期望上至少减半”，并应用标准的集中不等式。它还适用于没有组可以大于s个副本的情况，在这种情况下，下限是Ω(log n log s)。
2
你的论点适用于按顺序执行二分查找以寻找边界的算法类别。可能还有其他方法，因此写上“每个确定性算法”有些牵强。你的论点非常有价值，而且相当聪明，解决了可能在每个人脑海中的方法。我只会放弃“每个确定性算法”的部分。 - Bolo
1
你说得对，这确实是一个通用的论点，看起来很有说服力。（对我来说唯一值得怀疑的部分是，即使之前进行了探测，对手是否仍然可以使一侧变成奇数，但是，是的，它可以。）非常好的答案！ - ShreevatsaR
1
我并不完全相信。为什么每个算法都必须找到边界？我们为什么需要有关于边界的信息呢？即使假设每个算法都必须以某种方式确定边界，我们如何确保后续边界的探测时间为Omega(logn)？ - Aryabhatta
1
一般而言，这是正确的，但对于此下限使用的输入集，_a priori_，两个不同边界的位置集可能会接触但不重叠，从而防止那种推断。 - user382751
1
由于这不是一个“真正”的问题，我认为“现实”的模型为什么要有参数K没有道理。尽管如此，对于N个元素和任意一个元素最多K个副本，这个论点很容易推广到产生Ω(log N log K)的下限。 - user382751
显示剩余11条评论
15
一个有序数组暗示着二分查找。我们必须重新定义相等和比较。相等意味着元素数为奇数。我们可以通过观察组的第一个或最后一个元素的索引来进行比较。在奇数组之前，第一个元素将是偶数索引(从0开始)，在奇数组之后将是奇数索引。我们可以使用二分查找找到一组的第一个和最后一个元素。总成本为O((log N)²)。
O((log N)²)的证明
  T(2) = 1 //to make the summation nice
  T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements

对于一些N=2^k的情况，

T(2^k) = (log 2^k) + T(2^(k-1))
       = (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
       = (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
       = k + (k-1) + (k-2) + ... + 1
       = k(k+1)/2
       = (k² + k)/2
       = (log(N)² + log(N))/ 2
       = O(log(N)²)
1
吹毛求疵：一个O(log N)算法也是一个O(log<sup>2</sup> N)算法。Ω在这里更有趣。 - Matthieu M.
1
@Matthieu... 还挑毛病：Theta 更有趣 :-) - Aryabhatta
1
@Moron：是的，我猜是这样:p 然而，当前的讨论似乎演变成证明在少于log2 N的时间内不可能完成它。尽管如此，我仍然不明白如何证明它，排序算法证明了在给定某些约束条件下，可以获得比常见模型建议更好的渐近性能，因此我想知道是否可以在这里应用它。 - Matthieu M.
另一方面，尽管包含 0、1 和 2 的输入最适合使用 O(n) 计数排序，但二分查找仍具有 Θ(log n) 查询的最优性能。 - user382751
@ShreevatsaR：我同意，为什么这里更不优化的算法会得到赞成？ - Dean J
显示剩余2条评论
11

查看数组的中间元素。通过适当的二分搜索，您可以找到该元素在数组中第一次出现和最后一次出现的位置。例如，如果中间元素是'a'，则您需要按照下面所示找到i和j：

[* * * * a a a a * * *]
         ^     ^ 
         |     |
         |     |
         i     j

j - i 是偶数吗？如果是，你就完成了！否则（这是关键），需要问的问题是i是偶数还是奇数? 你明白这个知识点意味着什么吗？然后剩下的就很容易了。

啊，我看到杰瑞泄漏了！ :) - Dimitris Andreou
2
如果 j-i 是偶数，那么你必须使用一半的数组重复算法。第 i 次迭代需要 (log N) - i 步，因此您需要 O( (log N)^2 ) 步。 - Pete Kirkham
不完全是这样。在第i次迭代中，这两个二分查找只需要log(N / 2^i) - 在每一步中，我必须对其进行两个二分查找的数组部分至少减半。 - Dimitris Andreou
1
@Dimitris - 你可以通过每次只在一个边界上搜索来减少近一半的二分查找次数。有一半的时间你会在更大的一侧找到奇数计数，但你不需要担心不平衡的二分法。要做到这一点，你需要大量重复相同值，当它跨越当前范围的中心时，处理起来非常快，因此这不是最坏情况。 - user180247
1
@Dimitris log(N / 2^i) = log(N) - i，因此它确实是O(log(n)^2)。 - Rotsor
@Steve314 也是对的。虽然我不认为这会影响大O分析。仍然想知道没有对输入做任何假设的O(logn)解决方案是什么。 - Dimitris Andreou
6
这篇文章是为了支持“throwawayacct”发布的答案而写的，他应该获得奖励。我花了一些时间来回答这个问题，我完全相信他的证明是正确的，你需要Ω(log(n)^2)的查询才能找到出现奇数次的数字。我相信这是正确的，因为我在浏览他的解决方案后重新创建了完全相同的论点。
在解决方案中，对手创建了一个输入，使算法难以处理，但对人类分析器来说却很简单。该输入由k个每个都有k个条目的页面组成。总条目数为n = k^2，并且O(log(k)) = O(log(n))和Ω(log(k)) = Ω(log(n))非常重要。为了制作输入，对手制作了一个长度为k的字符串，形式为00...011...1，其中转换位于任意位置。然后，将字符串中的每个符号扩展为长度为k的页面，格式为aa...abb...b，在第i页上，a = i，b = i + 1。每个页面上的转换也位于任意位置，除了奇偶性与扩展自该页面的符号相匹配外。
了解“对手方法”来分析算法的最坏情况非常重要。对手回答有关算法输入的查询，而不承诺未来的答案。答案必须一致，并且当对手被困住足以让算法得出结论时，游戏就结束了。
有了这些背景，以下是一些观察结果：
1）如果要通过在页面中进行查询来学习过渡的奇偶性，则必须学习过渡的确切位置，并且需要Ω(log(k))个查询。任何一组查询都将转换点限制为一个区间，任何长度超过1的区间都具有两种奇偶性。查找该页面中转换的最有效方法是二分查找。
2）最微妙和最重要的一点：有两种方法可以确定特定页面内部的转换的奇偶性。您可以在该页面中进行足够的查询以找到转换，或者如果在较早和较晚的页面中发现相同的奇偶性，则可以推断出奇偶性。没有逃脱这个二选一的可能。任何一组查询都将每个页面中的转换点限制为某个区间。唯一对奇偶性的限制来自长度为1的区间。否则，转换点可以自由摆动以具有任何一致的奇偶性。
3）在对手方法中，没有幸运的打击。例如，假设您在某个页面中的第一个查询是朝着一个端而不是中间。由于对手没有承诺答案，因此他可以将转换放在长侧上。
4）最终结果是，您被迫直接探测Ω(log(k))个页面中的奇偶性，并且每个子问题的工作量也为Ω(log(k))。

5) 随机选择并不比对手选择更好。数学上更加复杂，因为现在您可以获得部分统计信息，而不是严格的是或否。但这几乎没有任何区别。例如，您可以给每个页面长度k ^ 2，以便高概率下，每个页面中的前log（k）个查询几乎不会告诉您有关该页面奇偶性的信息。对手可以在开始时进行随机选择，它仍然有效。

哎呀，看起来我们都想重写这个参数 :P - user382751
所以就这样吧。我并不是只想重写我的答案，而是想作为注释或摘要。也许它仍然有用。 - Greg Kuperberg
确实非常有用。在throwawayacct重写后，我才能够理解他的证明，即使那样也很困难。您的解释非常清晰 - 希望我的数学教授也有类似的技能。感谢您的努力。赞！ - Dave O.
@Dave：非常感谢你，而且，像你这样的赞扬会帮助我继续前进。 - Greg Kuperberg
@GregKuperberg 你认为这种方法怎么样？假设我们通过反复执行以下步骤来进行：1）将R定义为剩余搜索空间中长度为偶数的元素范围的中心。2）检查R的端点。3）如果它们相同，则从搜索空间中删除R；如果不是，则在R上进行二分搜索以找到R中的边界，时间复杂度为log R。即，我们要么在O（1）中通过R减少搜索空间，要么在O（R）中减少约一半。 - Dave
@DaveGalvin - 无论如何，在最坏的情况下它都无法帮助，因为user382751证明它是Ω(log(n)^2)，而且很容易看出它是O((log N)^2)。可能R在最坏的情况下也太短了，不能给你太多帮助。 - Greg Kuperberg
5
从数组中间开始向后遍历，直到找到一个与中心值不同的数。检查边界上面的数字在奇数索引位置还是偶数索引位置。如果它是奇数，则出现奇数次的数字在左侧，因此请在开始和找到的边界之间重复搜索。如果它是偶数，则出现奇数次的数字必须在数组的后半部分，因此请在右半部分重复搜索。
如上所述，这个算法既有对数部分又有线性部分。如果您希望整个过程都是对数级别的，请使用二分查找而非向后遍历数组到不同的值。但是，除非您期望有很多相同数字的重复，否则进行二分查找可能没有太大意义。
1
在最坏情况下，你重复进行了log n次二分查找，这不是O((log n)^2)吗？ - IVlad
@IVlad：不完全是这样——在每次搜索之后，你都会丢弃（至少）一半的数组元素，因此在每次后续搜索中，你要搜索的数量也会对数减少。 - Jerry Coffin
3
(log n)+(log n/2)+(log n/4)+... = log(n^(log n)*2^(-(log n)((log n)-1)/2)) = (log n)²-(log n)((log n)-1)/2 = (log n)²/2+(log n)/2 = O((log n)²) 可以翻译为：对于给定的数值n，求(log n)+(log n/2)+(log n/4)+...的和。答案为log(n^(log n)*2^(-(log n)((log n)-1)/2))。此表达式可以进一步化简为(log n)²-(log n)((log n)-1)/2。再将其转换为二次方程组(log n)²/2+(log n)/2，最终得出结果为O((log n)²)。在WolframAlpha中输入"sum log_2(2^k/2^i) for i=0..k-1"可得相同的结果。 - Nabb
1
是的，但为了丢弃那一半，您需要运行另一个二分查找，这使得时间复杂度变为对数平方。我认为发布一些伪代码会更清楚明了。 - IVlad
3
我有一个算法可以在 log(N/C)*log(K) 的时间内运行，其中 K 是最大同值范围的长度，C 是要搜索的范围的长度。
这个算法与以前发布的大多数算法的主要区别在于它利用了所有相同值范围都很短的情况。它不是通过对整个数组进行二分查找来找到边界，而是首先通过后退1、2、4、8等（log(K)次）步骤快速找到一个粗略估计值，然后再通过二分查找结果范围 (再次使用 log(K))。
该算法如下（用 C# 编写）：
// Finds the start of the range of equal numbers containing the index "index", 
// which is assumed to be inside the array
// 
// Complexity is O(log(K)) with K being the length of range
static int findRangeStart (int[] arr, int index)
{
    int candidate = index;
    int value = arr[index];
    int step = 1;

    // find the boundary for binary search:
    while(candidate>=0 && arr[candidate] == value)
    {
        candidate -= step;
        step *= 2;
    }

    // binary search:
    int a = Math.Max(0,candidate);
    int b = candidate+step/2;
    while(a+1!=b)
    {
        int c = (a+b)/2;
        if(arr[c] == value)
            b = c;
        else
            a = c;
    }
    return b;
}

// Finds the index after the only "odd" range of equal numbers in the array.
// The result should be in the range (start; end]
// The "end" is considered to always be the end of some equal number range.
static int search(int[] arr, int start, int end)
{
    if(arr[start] == arr[end-1])
        return end;

    int middle = (start+end)/2;

    int rangeStart = findRangeStart(arr,middle);

    if((rangeStart & 1) == 0)
        return search(arr, middle, end);
    return search(arr, start, rangeStart);
}

// Finds the index after the only "odd" range of equal numbers in the array
static int search(int[] arr)
{
    return search(arr, 0, arr.Length);
}
我没有完全阅读你的代码，但是+1给你，因为你似乎是第一个观察到“K”必须成为问题复杂度的一部分的人。也许你可以添加一些文字描述你的想法？ - Jens Gustedt
2

取中间元素e。使用二分查找找到第一个和最后一个出现的位置。O(log(n)) 如果是奇数，则返回e。 否则，递归到具有奇数个元素的一侧[....]eeee[....]

运行时间将为log(n) + log(n/2) + log(n/4).... = O(log(n)^2)。

1

您可以使用这个算法：

int GetSpecialOne(int[] array, int length)
{
   int specialOne = array[0];

   for(int i=1; i < length; i++)
   {
      specialOne ^= array[i];
   }
   return specialOne;
}

在http://www.technicalinterviewquestions.net上可以找到一个类似的问题这里，得以解决。

1

啊哈。有答案了。

进行二分查找，对于每个值，向后移动，直到找到具有相同值的第一个条目。如果其索引为偶数，则在奇怪的元素之前，因此向右移动。
如果其数组索引为奇数，则在奇怪的元素之后，因此向左移动。

伪代码（这是一般想法，未经测试...）：

    private static int FindOddBall(int[] ary)
    {
        int l = 0,
            r = ary.Length - 1;
        int n = (l+r)/2;
        while (r > l+2)
        {
            n = (l + r) / 2;
            while (ary[n] == ary[n-1])
                n = FindBreakIndex(ary, l, n);
            if (n % 2 == 0) // even index we are on or to the left of the oddball 
                l = n;
            else            // odd index we are to the right of the oddball
                r = n-1;
        }
        return ary[l];
    }
    private static int FindBreakIndex(int[] ary, int l, int n)
    {
        var t = ary[n];
        var r = n;
        while(ary[n] != t || ary[n] == ary[n-1])
            if(ary[n] == t)
            {
                r = n;
                n = (l + r)/2;
            }
            else
            {
                l = n;
                n = (l + r)/2;
            }
        return n;
    }
我不这么认为，因为这个算法是基于二分查找的...将数组大小加倍不会使迭代次数加倍，只会增加1...据我所知，这是O(n)。 - Charles Bretana
2
@Charles Breatana - 将数组的大小加倍将会使您的算法迭代次数加倍。考虑一个由n-1个相等数字和另外一个数字组成的数组。您最内层的while循环是O(n)，因为它将遍历n/2个元素。 - IVlad
3
@Charles Bretana - 特殊情况与否，都使得您当前的算法为O(n)。我没有看到任何编辑，但是如果我们正在考虑相同的事情，它仍然不会是O(log n)而是O((log n)^2)。 - IVlad
2
为什么要使用晦涩难懂的变量名？ - Svante
@IVlad，您可能对O((log n) ^2)的说法是正确的。通常情况下，嵌套二进制迭代会给您提供O((log n) ^2)，正如您所说，但我认为这种情况可能有所不同，因为在这里它们不是完全独立的嵌套迭代。内部和外部迭代都不必迭代每个元素，只需迭代不被另一迭代淘汰的那些元素即可...这肯定会减少所需的处理步骤数量，并可能缓解算法的“O-ness”（尽管我必须承认我不确定如何精确计算）。 - Charles Bretana
显示剩余8条评论
0

试试这个：

int getOddOccurrence(int ar[], int ar_size)
{
     int i;
     int xor = 0; 
     for (i=0; i < ar_size; i++)     
        xor = xor ^ ar[i];

     return res;
}

XOR 操作每次与相同的数字进行 XOR 运算时都会被取消，因此 1^1=0，但是 1^1^1=1，所以每对数字应该被取消，留下奇数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接