编程测试 - Codility - Dominator [英] Programming Test - Codility - Dominator
问题描述
我只是遇到了一个严密的问题给了我一些困难时间，我仍在努力弄清楚如何满足空间和时间复杂性的限制。
I just had a codility problem give me a hard time and I'm still trying to figure out how the space and time complexity constraints could have been met.
问题如下：
数组中的主要成员是占据阵列中一半以上位置的成员，例如：
The problem is as follows: A dominant member in the array is one that occupies over half the positions in the array, for example:
{3,67 ，23,67,67}
{3, 67, 23, 67, 67}
67是一个主导成员，因为它出现在数组中的3/5（> 50％）位置。
67 is a dominant member because it appears in the array in 3/5 (>50%) positions.
现在，您需要提供一个接收数组的方法，如果存在，则返回显性成员的索引，如果没有，则返回-1。
Now, you are expected to provide a method that takes in an array and returns an index of the dominant member if one exists and -1 if there is none.
简单，对吗？好吧，如果不是因为以下限制，我可以轻松解决问题：
Easy, right? Well, I could have solved the problem handily if it were not for the following constraints:
- 预期时间复杂度为O（n）
- 预期的空间复杂度为O（1）
我可以看到你如何为O解决这个问题（n）具有O（n）空间复杂度的时间以及具有O（1）空间复杂度的O（n ^ 2）时间，但不是满足O（n）时间和O（1）空间的时间。
I can see how you could solve this for O(n) time with O(n) space complexities as well as O(n^2) time with O(1) space complexities, but not one that meets both O(n) time and O(1) space.
我真的很感激能看到这个问题的解决方案。别担心，截止日期已经过了几个小时（我只有30分钟），所以我不是想欺骗。谢谢。
I would really appreciate seeing a solution to this problem. Don't worry, the deadline has passed a few hours ago (I only had 30 minutes), so I'm not trying to cheat. Thanks.
推荐答案
用 BFPRT ，又称中位数中位数（O（N）时间，O（1）空间）。然后扫描数组 - 如果一个数字占主导地位，则中位数将等于该数字。遍历数组并计算该数字的实例数。如果它超过阵列的一半，它就是统治者。否则，就没有统治者。
Find the median with BFPRT, aka median of medians (O(N) time, O(1) space). Then scan through the array -- if one number dominates, the median will be equal to that number. Walk through the array and count the number of instances of that number. If it's over half the array, it's the dominator. Otherwise, there is no dominator.
这篇关于编程测试 - Codility - Dominator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
