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

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

由于这个算法是2n，所以它属于O(n)。

我们没有关于数组内部长度分布以及整个数组的任何信息，对吧？

因此，数组长度可能是1、11、101、1001或其他一些长度，至少为1且没有上限，并且必须包含至少1种类型的元素（“数字”），最多包含（长度-1）/2 + 1个元素，总大小为1、11、101：1、1到6、1到51个元素等等。

我们应该假设每种可能的大小具有相等的概率吗？这将导致子数组的中间长度为size/4，对吧？

一个大小为5的数组可以被分成1、2或3个子列表。

如果我们深入细节，显而易见的事情并不那么明显。

一个大小为5的数组可以通过一种方式“分割”成一个子列表，但这种方式有争议，是否称之为“分割”都说不清楚。它只是一个由5个元素组成的列表（aaaaa）。为避免混淆，让我们假设列表内部的元素是有序字符，而不是数字（a、b、c等）。

线索是你正在寻找log(n)。这比n小。

一次一个地遍历整个数组？那是n。那行不通。

我们知道数组中的前两个索引（0和1）应该是相同的数字。如果奇数在它们之后，50和51也是如此。

因此，在数组中找到中间元素，将其与右侧元素进行比较。如果数字的变化发生在错误的索引上，我们就知道数组中的奇数在它之前；否则，它在之后。通过一组比较，我们确定目标所在的数组的哪一半。

从那里继续。

假设索引从0开始。二分查找最小的偶数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];
}