如何在O（n）时间的SORTED数组中find出现奇数次的数字？
我有一个问题，我试图一遍又一遍地思考这个问题，但没有在这里发表这个问题。 也许我可以从别人的angular度来看待这个问题，试着让它发挥作用。
问题是：我们得到一个SORTED数组，其中包含偶数次出现的值的集合，除了出现ODD次数的值之外。 我们需要在日志中find解决scheme。
在O（n）时间很容易find解决scheme，但在日志中执行看起来相当棘手。
定理 ： 这个问题的每个确定性algorithm在最坏的情况下探测Ω（log 2 n）个存储单元。
certificate （完全改写为更正式的风格）：
设k> 0是一个奇数整数，令n = k 2 。 我们描述了一个强制（log 2 （k + 1）） 2 =Ω（log 2 n）个探测器的对手。
我们称之为相同元素组的最大子序列。 攻击者可能的input包括k个长度为k的分段 x 1 x 2 … x k 。 对于每个片段x j ，存在一个整数b j∈ [0，k]，使得x j包含j – 1的b个j个拷贝，然后是j的k个b个拷贝。 每个组最多重叠两个段，每个段最多重叠两个组。
Group boundaries | | | | | 0 0 1 1 1 2 2 3 3 | | | | Segment boundaries 无论哪里增加2个，我们都按照惯例假设双重边界。
Group boundaries | || | | 0 0 0 2 2 2 2 3 3
要求 ： 第j组边界（1≤j≤k）的位置由段x j唯一确定。
certificate ：在（（j-1）k + b j ）存储位置之后，x j唯一确定b j 。 //
我们说，algorithm已经观察到第j组边界，以防其xj的探测结果唯一确定xj 。 按照惯例，始终观察input的开始和结束。 该algorithm有可能唯一确定组边界的位置而不观察它。
Group boundaries | X | | | 0 0 ? 1 2 2 3 3 3 | | | | Segment boundaries
给定只有0 0，algorithm不能确定是否？ 是0还是1.在上下文中，但是，？ 必须是1，否则会有三个奇数组，并且可以推断在X处的组边界。 这些推论对于对手来说可能是有问题的，但是事实certificate，只有在问题的群体边界是“不相关的”之后才能做出这些推论。
要求 ： 在algorithm执行期间的任何给定点，考虑它观察到的一组组边界。 连续的一对是奇数的，奇数组是在它们之间。
certificate ：每个其他连续的对只限于偶数组。 //
定义由特殊连续对限定的奇长序列作为相关子序列 。
要求 ： 相关子序列内部的组边界是唯一确定的。 如果至less有一个这样的边界，那么奇数组的身份不是唯一确定的。
certificate ：在不失一般性的情况下，假定每个存储器位置都不在相关的子序列中，并且相关子序列中包含的每个片段恰好有一个未被探测到的位置。 假设第j组边界（称为B）位于相关子序列的内部。 通过假设，对xj的探测决定了B的位置达到两个连续的可能性。 我们把它称为距左边观察到的奇数左边和另一个奇数右边的距离。 对于这两种可能性，我们从左到右进行工作，并确定每个剩余的内部组边界的位置，以使其左边的组是均匀的。 （我们可以这样做，因为它们每个都有两个连续的可能性。）如果B在奇数左边，那么在其左边的组是奇数奇数组。 如果B在奇数右边，则相关子序列中的最后一个组是唯一奇数组。 两者都是有效的input，所以该algorithm既没有唯一确定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
作为这一说法的结果，该algorithm， 不pipe它是如何工作的 ，都必须将相关的子序列缩小到一个组。 根据定义，因此它必须遵守一些小组边界。 敌人现在有尽可能多的可能性的简单任务。
在algorithm执行期间的任何给定点，攻击者在内部承诺对于相关子序列之外的每个存储器位置的一种可能性。 一开始，相关的子序列就是整个input，所以没有初始的承诺。 每当algorithm探测x j的未提交位置时，攻击者必须提交两个值之一：j – 1或j。 如果它能避免让第j 个边界被观察到，它就会select一个剩下的可能性的至less一半（就观察而言）。 否则，select在相关区间内至less保留一半的群体，为其他群体提供价值。
这样，攻击者迫使algorithm至less观察log 2 （k + 1）组边界，并且在观察第j组边界时，algorithm至less要做log 2 （k + 1）个探测。
扩展：
这个结果直接扩展到随机化algorithm，通过对input进行随机化，从algorithm的angular度，用“最多减半”代替“最多减半”，并应用标准的浓度不等式。
它也延伸到没有一个组可以大于s副本的情况; 在这种情况下，下限是Ω（log n log s） 。
sorting的数组表示一个二进制search。 我们必须重新界定平等和比较。 平等简单意味着奇数个元素。 我们可以通过观察小组的第一个或最后一个元素的指数来进行比较。 第一个元素将是奇数组之前的偶数索引（基于0的索引），奇数组之后的奇数索引。 我们可以使用二分查找find一个组的第一个和最后一个元素。 总成本是O（（log N）2）。
O（（log N）2）的certificate
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)²)
看看数组的中间元素。 通过一些适当的二进制search，您可以在数组中find第一个和最后一个外观。 例如，如果中间元素是“a”，则需要find如下所示的i和j ：
[* * * * aaaa * * *] ^ ^ | | | | ij
是j - i是一个偶数？ 你完成了！ 否则（这里是关键），要问的问题是我是偶数还是奇数 ？ 你知道这个知识蕴涵了什么吗？ 其余的很容易。
这个答案是支持“throwawayacct”发布的答案。 他值得奖励。 我花了一些时间在这个问题上，我完全相信他的certificate是正确的，你需要Ω（log（n）^ 2）查询来查找出现奇数次的数字。 我深信，因为我只是在浏览他的解决scheme后重新创build了完全相同的论点。
在解决scheme中，对手创build一个input，使algorithm的生活变得困难，但对于人类分析器也很简单。 input由k个页面组成，每个页面有k个条目。 logging的总数是n = k ^ 2，重要的是O（log（k））= O（log（n））和Ω（log（k））=Ω（log（n））。 为了进行input，攻击者以00 … 011 … 1的forms创build一个长度为k的string，并在任意位置进行转换。 然后将string中的每个符号展开为forms为aa … abb … b的长度为k的页面，其中在第i页上a = i和b = i + 1。 每个页面上的转换也处于任意位置，除了奇偶校验符合页面扩展的符号。
理解分析algorithm最坏情况的“对手方法”是很重要的。 对手回答关于algorithminput的查询，而不会提交将来的答案。 答案必须是一致的，当敌手被locking足够的algorithm来达成结论时，游戏结束。
有了这个背景，下面是一些观察：
1）如果要通过在该页面中查询来了解页面中的转换奇偶性，则必须了解转换的确切位置，并且需要Ω（log（k））个查询。 任何查询集合都会将转换点限制为一个间隔，并且任何长度大于1的间隔都有两个奇偶校验。 在该页面中转换的最有效的search是二进制search。
2） 最微妙也是最重要的一点：有两种方法可以确定特定页面内的转换奇偶校验。 您可以在该页面中进行足够的查询以查找转换，或者如果在较早和较晚的页面中find相同的奇偶校验，则可以推断奇偶校验。 这也没有逃脱，或者。 任何一组查询都将每个页面中的转换点限制在一定的时间间隔内。 对奇偶的唯一限制来自长度为1的区间。否则，过渡点可以自由地摆动以获得任何一致的奇偶。
3）在对手的方法中，没有幸运的打击。 例如，假设你在某个页面中的第一个查询是朝着一端而不是在中间。 由于对手没有答复，所以他可以自由地把过渡放在一边。
4）最终的结果是，你不得不直接在Ω（log（k））页面中检查奇偶校验，这些子问题的每一个的工作也是Ω（log（k））。
5）随机select的东西比对抗select好得多。 math是比较复杂的，因为现在你可以得到部分的统计信息，而不是一个严格的是你知道一个平价或不，你不知道它。 但是它没有什么区别。 例如，您可以给每个页面长度k ^ 2，以便以较高的概率，每个页面中的第一个log（k）查询几乎不会告诉您该页面上的奇偶校验。 对手可以在开始时进行随机select，它仍然有效。
从数组中间开始向后走，直到find与中心值不同的值。 检查边界上方的数字是否在奇数或偶数索引处。 如果是奇数，那么奇数次出现在左边，所以在search到的开始和边界之间重复search。 如果是偶数，那么出现奇数次的数字必须在数组后面，所以在右半部分重复search。
如上所述，这既有对数也有线性分量。 如果你想保持整个事物的对数，而不是只是向后走过一个不同的数组，而是想用二进制search。 除非你期望许多重复的相同数字，二进制search可能不值得。
我有一个在log（N / C）* log（K）中工作的algorithm，其中K是最大同值范围的长度，C是正在search的范围的长度。
这个algorithm最大的区别就是它利用了所有相同值范围都很短的情况。 它不是通过二进制search整个数组来find边界，而是首先通过跳回1,2,4,8，…（log（K）迭代）步骤来快速find粗略的估计，然后二进制search得到的范围（log（K）再次）。
algorithm如下（用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); }
以中间元素e。 使用二进制search来查找第一个和最后一个事件。 O（log（n））如果是奇数返回e。 否则，recursion到具有奇数个元素的一侧[…] eeee [….]
运行时将是log（n）+ log（n / 2）+ log（n / 4）…. = O（log（n）^ 2）。
唉唉。 有一个答案。
进行二分search，search每个值，向后移动，直到find具有相同值的第一个条目。 如果它的指数是偶数，那就是在古怪之前，所以向右移动。
如果它的数组索引是奇数，则是在古怪之后，所以向左移动。
在伪代码（这是一般的想法，没有testing…）：
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; }
你可以使用这个algorithm：
int GetSpecialOne(int[] array, int length) { int specialOne = array[0]; for(int i=1; i < length; i++) { specialOne ^= array[i]; } return specialOne; }
解决了类似的问题，可以在这里findhttp://www.technicalinterviewquestions.net
我们没有任何关于数组内部的长度分布以及整个数组的详细信息，对吗？
所以排列长度可能是1，11，101，1001或者1，至less没有上限，并且必须至less包含1个元素（'数字'）到（length-1）/ 2 + 1元素，总尺寸为1,11,101：1,1至6,1至51个元件等。
我们应该假设所有可能的概率相等吗？ 这将导致大小为4的子arrays的中间长度，不是吗？
一个大小为5的数组可以分成1,2或3个子列表。
如果我们详细讨论，似乎显而易见的事情并不那么明显。
一个大小为5的数组可以用一种方法“划分”成一个子列表，有争议的权利称之为“划分”。 这只是5个元素（aaaaa）的列表。 为了避免混淆，我们假设列表中的元素是有序的字符，而不是数字（a，b，c，…）。
分为两个子列表，可能是（1，4），（2,3），（3，2），（4，1）。 （abbbb，aabbb，aaabb，aaaab）。
现在让我们回顾一下之前提出的主张：“分裂”（5）是否应该被假定为4个分裂成2个次级分的相同概率？ 或者我们将它们混合在一起，并假设每个分区的概率是平均的（1/5）？
或者我们可以计算解决scheme而不知道子列表长度的概率？
线索是你正在寻找log（n）。 这比n小。
一个一个地走过整个arrays？ 那是n。 这是行不通的。
我们知道数组中的前两个索引（0和1）应该是相同的数字。 与50和51相同，如果数组中的奇数在它们之后 。
因此，find数组中的中间元素，并将其与元素之后的元素进行比较。 如果数字的变化发生在错误的索引上，我们知道数组中的奇数在它之前; 否则，在之后。 通过一组比较，我们计算出目标所在arrays的哪一半。
继续走下去。
使用一个哈希表
For each element E in the input set if E is set in the hash table increment it's value else set E in the hash table and initialize it to 0 For each key K in hash table if K % 2 = 1 return K
由于这个algorithm是2n它属于O（n）
尝试这个：
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，所以每一对都应该抵消掉剩下的奇数。
您可以创build一个累积数组并计算每个数字出现的次数，然后在cummulative数组中find奇数元素。 例：
int a[]=new int[]{2,3,4,2,3,1,4,5,6,5,6,7,1}; int b[]=new int[1000]; for (int i=0;i<b.length;i++) { b[i]=0; } for (Int i=0;i<a.length;i++) { b[a[i]]++; } for (int i=0;i<b.length;i++) { if ( b[i]!=0) { if (b[i] %2==0) { system.out.println(i); break; } }
假定索引从0开始。二进制search最小的偶数i，使得x [i]！= x [i + 1]; 你的答案是x [i]。
编辑：由于公众需求，这里是代码
int f(int *x, int min, int max) { int size = max; min /= 2; max /= 2; while (min < max) { int i = (min + max)/2; if (i==0 || x[2*i-1] == x[2*i]) min = i+1; else max = i-1; } if (2*max == size || x[2*max] != x[2*max+1]) return x[2*max]; return x[2*min]; }
