algorithm - 如何编写返回数组中多数元素的伪代码？

Question

我正在研究教科书算法(Dasgupta、C. H. Papadimitriou 和 U. V. Vazirani)，我试图解决教科书问题 2.23。 但是，我不确定我的解决方案是否正确。感谢任何网站!

给定一些限制:

n = 2^k,k ∈ N

Runtime = O(n log n)

Use at most O(1) additional memory.

我想为一个函数编写伪代码，该函数返回数组 B = [b_1,...,b_n] 的 length n with b_i ∈ B 中的多数元素code>，其中只能使用等式和不等式 (b_i = b_j) 的测试。

如果元素 x 出现超过 n/2 次，则称为多数元素:

MajorityElement(A,x) := |{i | i ∈ {1,...,n},b_i = x}| > n/2

给定子数组 B_l,_r = [a_l , . . . , a_r ] 我想到了使用分而治之的算法:

 function GetMajorityElement(B, l, r, x):
            if x = 1: -- so here I check if array has only one element
                return B[1]
            else l < r: --- here I check if left element < right element 
                midelement<–(l+r-1)/2
                B_lefthalf <– B[ :midelement]
                B_rightthalf <– B[midelement:]
            MEL = GetMajorityElement(B_lefthalf) - recursively repeat
            MER = GetMajorityElement(B_rightthalf)

            if MEL is a majority element of B:
                           return MEL
            if MER is a majority element of B:
                           return MER
            return ‘no majority’

我假设算法运行:T (n) = 2T(n/2) + O(n) = O(n log n)。

感谢任何现场/提示和更正。谢谢!

Answer 1

为了找到多数元素，我们使用一种称为摩尔投票算法的基本算法。

算法是:

1. 初始化索引和多数元素的计数

     maj_index = 0, count = 1
   

2. 循环 i = 1 到 size – 1 ......

   (a) If a[maj_index] == a[i]
         count++
   (b) Else
       count--;
   (c) If count == 0
         maj_index = i;
         count = 1
   

3. 返回一个[maj_index]