分而治之 - 多元阵

Question

我想设计一种算法,确定数组A是否为复数,并返回该元素.

如果阵列中的一半以上与x相同,则阵列中存在元素x时,数组为多个.

我想知道是否有一个更有效的分而治之算法运行比我现在的更好.

Assume you have the array

aaabbcac

我将递归分割数组,直到我得到大小为2的子数组,如下所示.

aa ab bc ac

从这里开始,我将比较SUBARRAY中的每个元素以查看它们是否相等:如果是EQUAL,则返回元素,Else,返回false.

aa ab bc ac 
a  f   f  f

所以现在我有一个元素A和3的数组.

我正在考虑将它们组合起来:

a  f  f  f
  a     f  <----- combining a and f will give a
     a    <----- returns a

但是,如果我们查看数组,我们有4个A,它不符合复数数组的标准.如果数组不是复数数组,它应该返回false.

我相信我的算法将在O(n lgn)中运行,如果它是一个正确的算法,遗憾的是它不是.

任何人都能指出我正确的方向吗？

Answer 1

这是一个计算 出现次数的问题x。将数组拆分为子数组并x与子数组一起发送。返回计数、总计数并检查它是否大于数组的大小。