编程测试 - Codility - Dominator

Question

我只是遇到了一个问题,给我带来了困难,我仍在努力弄清楚如何满足空间和时间复杂性的限制.

问题如下:数组中的主要成员是占据阵列中一半以上位置的成员,例如:

{3,67,23,67,67}

67是主导成员,因为它在阵列中出现在3/5(> 50%)位置.

现在,您需要提供一个接收数组的方法,如果存在,则返回显性成员的索引,如果没有,则返回-1.

容易,对吗？好吧,如果不是因为以下限制,我可以轻松地解决问题:

• 预期时间复杂度为O(n)
• 预期的空间复杂度为O(1)

我可以看到你如何用O(n)空间复杂度来解决这个问题,以及O(1)空间复杂度的O(n ^ 2)时间,但不能满足O(n)时间和O(1)空间.

我真的很感激能够找到解决这个问题的方法.别担心,截止日期已经过了几个小时(我只有30分钟),所以我不是想欺骗.谢谢.

Answer 1

谷歌搜索"计算阵列的主导成员",这是第一个结果.请参阅第3页上介绍的算法.

element x;
int count ? 0;
For(i = 0 to n ? 1) {
  if(count == 0) { x ? A[i]; count++; }
  else if (A[i] == x) count++;
  else count??;
}
Check if x is dominant element by scanning array A

基本上观察一下,如果你在数组中找到两个不同的元素,你可以删除它们而不改变余数上的主导元素.这段代码只是不断抛出不同的元素对,跟踪它看到单个剩余未配对元素的次数.

Answer 2

用BFPRT求中位数,即中位数中位数(O(N)时间,O(1)空间).然后扫描数组 - 如果一个数字占优势,则中位数将等于该数字.遍历数组并计算该数字的实例数.如果它超过阵列的一半,它就是统治者.否则,就没有统治者.