c++ - 搜索排序数组中出现次数超过一半的元素所需的最小比较

Question

最近，我收到了一个问题，要找到从n给定元素中搜索元素所需的最小比较，前提是它们是sorted，并且出现次数超过 half( n/2)。

例如。给定排序数组为：1,1,2,2,2,2,2,7,11。这个数组的大小是：9。我们需要找到找到所需的最小比较2（因为它有超过 n/2 次出现（5）。

什么是最好的算法，最坏的情况是什么？

提供的选项是：

i) O(1)

ii) O(n)

iii) O(log(n))

iv) O(nlog(n))

Answer 1

前提是它们已排序

在这种情况下，您只需检查一个中间元素，如果事实是

出现超过一半 (n/2)

有保证

Answer 2

这个问题可以有两种可能的解释。我会解释两者。

首先，如果问题假设肯定有一个数字出现n/2或多次出现，那么 MBo 的答案就足够了。

但是，如果有可能没有元素n/2出现，则复杂度为O(log(n))。我们不能只检查n/2th元素。例如，在 array2, 4, 6, 6, 6, 8, 10中，中间元素是6，但它没有出现n/2或出现多次。这种情况的算法如下：

• 选择中间元素（比如x）。
• lIndex使用二分搜索（比如）在左子数组中找到 x 的索引。
• rIndex使用二分搜索（比如）在右子数组中找到 x 的索引。
• 如果rIndex - lIndex >= n/2，则该次数出现n/2或多次。否则，不存在这样的数字。

由于我们使用二分查找来查找左右子数组中的数字，因此上述算法的复杂度为O(log(n)).