找到一个恰好N/2次的数字

这是我的一个面试问题.给定N个元素的数组,其中元素恰好出现N/2次,其余N/2个元素是唯一的.你如何找到运行时间更好的元素？

请记住元素没有排序,你可以假设N是偶数.例如,

input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }

所以这里10次出现5次,即N/2次.

我知道O(n)运行时的解决方案.但仍期待通过O(log n)了解更好的解决方案.

1> 小智..：

---

如果您准备好接受很小的错误概率,那么有一个恒定的时间解决方案.从数组中随机抽取两个值,如果它们相同,则找到您要查找的值.在每一步,你有0.75的概率未完成.并且因为对于每个epsilon,存在一个n使得(3/4)^ n

还要注意的是,如果我们继续采样直到找到一对,预期的运行时间是恒定的,但最坏情况下的运行时间不受限制.

---

通常不大O意味着最坏情况？否则这不会那么难.

---

@Jeremy:没有大O并不意味着最糟糕的情况."大O最坏情况"意味着最坏的情况.big-O提供上限的事实有时让人们认为它必须描述最坏的情况,但事实并非如此.你可以在平均情况下得到渐近上界,而不是在最坏情况下也是渐近上界.那将是"大O平均情况".

2> Peter Recore..：

---

这是我尝试证明为什么不能在少于O(n)数组访问中完成这一操作(对于最坏的情况,这肯定是本例中唯一有趣的情况):

假设存在最坏情况的log(n)算法.该算法最多以log(n)次访问该数组.由于它不能假设哪些元素在哪里,让我选择它看到的哪个log(n)元素.我会选择给它第一个log(n)独特元素.它还没有找到重复,并且仍然存在n/2 - log(n)个独特元素供我根据需要提供它.实际上,在读取n/2个元素之前,我不能强迫它输入重复的数字.因此这种算法不可能存在.

从纯粹直观的角度来看,这似乎是不可能的.Log(40亿)是32个.所以有一个40亿个数组的数组,其中20亿个是唯一的,没有特别的顺序,有一种方法可以通过只检查32个元素来找到重复的元素？

---

请记住,O(log.n)不会自动暗示需要完全log_2(n)数组访问.对于常量a和b,您可以进行*log(n)+ b访问.[不是我认为这也可能]

---

未指定的问题不必是O(log(n)).如果声称它优于O(n),并且您已经通过提供列表的安排证明它必须执行至少n/2次查找,那么您声称该算法正好是O(n) )或更糟.

3> Don Johe..：

---

我认为你只需要解析数组,保持两个元素的积压.由于N/2相等且其余部分保证不同,因此在数组中必须有一个位置

a[i] == a[i-1] OR a[i] == a[i-2]

迭代一次通过你的数组,你有大约2*N的复杂性,它应该在O(N)内.

这个答案有点类似于Ganesh M和Dougie的答案,但我觉得有点简单.

4> cletus..：

---

您不能在次线性时间内执行此操作,因为您需要读取数组.要以对数时间处理一百万条记录的数组,只需要读取~20(log2)元素 - 显然是不可能的.毕竟如果你假设发现的第一个重复重复N/2次它仍然是O(n),因为你可能需要查看500,001个元素来找到重复.

如果假设整数是非负的,则可以在O(n)中执行此操作.它是这样的(伪Java):

int repeatedNumber = -1; // sentinel value
int count = 0;
BitSet bits = new BigSet(); // this bitset needs to have 2^31 bits, roughly 2.1 billion
boolean duplicate = false;
for (int i : elements) {
  if (bits[i].isSet()) {
    if (repeatedNumber == -1) {
      repeatedNumber = i;
      count = 1;
    } else if (i == repeatedNumber) {
      count++;
    } else {
      System.out.println("Array has more than one repeated element");
      duplicate = true;
      break;
    }
  } else {
    bits[i].set();
  }
}
if (!duplicate && repeatedNumber != -1 && count == elements.length/2) {
  System.out.println(repeatedNumber + " occurred " + count + " times. The rest of the elements are unique");
} else {
  System.out.println("Not true");
}

类似的方法用于对O(n)(基数排序)中的唯一整数数组进行排序.

---

+1可以很好地解释为什么这是一个虚假的问题.也许正确的答案是"你不能有这样的解决方案,这就是为什么"

5> Alex Martell..：

---

对于最坏情况的确定性行为,O(N)是正确的(我已经在前面的答案中看到过多个证明).

然而,现代算法理论并不仅仅关注最坏情况的行为(这就是为什么除了big-O之外还有很多其他的大事,即使懒惰的程序员匆忙经常使用big-O,即使他们想到的也是如此更接近于big-theta或big-omega ;-),也不仅仅是确定性(用米勒 - 拉宾素性测试......).

任何K 他们的概率主要测试方法;-).

这将是一个非常糟糕的面试问题.类似的不那么糟糕的问题经常被提出,经常被错误回答,并且经常被不成功的候选人误解.例如,一个典型的问题可能会被给定的N个项目的阵列,不知道是否有多数的项目,以确定是否有一个,并且它是哪一个,在O(N)时间和 O(1)的辅助space(所以你不能只设置一个哈希表或其他东西来计算不同值的出现次数).对于那个有价值的采访问题, "摩尔的投票方法"是一个很好的解决方案(可能是最好的解决方案).

另一个有趣的变化:如果你有10**1864位数字(总体上是8TB的数据,比如在bigtable或克隆上),以及你想要的多台机器,每个在相当快的局域网上有大约4GB的RAM,说一个比GB以太网好得多的 - 你如何在这些条件下对问题进行分类？如果你必须使用mapreduce/hadoop怎么办？如果您可以自由地为这一个问题设计自己的专用框架,那么您可以获得比使用mapreduce更好的性能吗？在包络后估计的粒度上有多好？我知道没有公布算法的这个变体的,所以如果你想检查与高度分布式的方法万亿级计算的候选人一般设施它可能是一个很大的考验......

6> Ganesh M..：

---

我的回答是,

将N个元素分成[N/3]个部分(即),每个部分将有3个元素.

现在将这3个元素相互比较.- 3次比较

至少其中一个部分将具有相同元素的两个副本.因此数量.

运行时 - O(N)

7> Crashworks..：

---

彼得是完全正确的.这是一种更正式的方式来重述他的证明:

设S是包含N个元素的集合.它是两个集合的并集为:p,其中包含一个符号α重复N/2倍,和q,其含有N/2唯一的符号ω ₁ ..ω _n/2个.S =p∪q.

假设在最坏的情况下,对于所有N> 2,存在一种能够在log(n)比较中检测重复数的算法.在最坏的情况下意味着不存在任何子集r⊂S,使得| r | = log ₂ N其中α∉r.

但是因为S =p∪q,所以有| p | S. | p |中的许多元素≠α = N/2,所以∀N/2,使得N/2≥日志₂ N,必须存在至少一个集合R⊂S,从而使| R | = log ₂ N和α∉r.任何N≥3都是这种情况.这与上述假设相矛盾,因此不能有任何这样的算法.

QED.

---

对于所有N> 2,

---

检测重复数的算法.在最坏的情况下意味着