一、主元素问题

    设
T[0..n-1]
是
n
个元素的数组。对任一元素
x
，设
S(x)={i|T[i]=x}
。当
|S(x)|>n/2
时，称
x
为
T
的主元素。

1) 
如果
T
中元素存在序关系，按分治策略设计并实现一个线性时间算法，确定
T[0..n-1]
是否有一个主元素。

2) 
若
T
中元素不存在序关系，只能测试任意两个元素是否相等，试设计并实现一个
O(nlogn)
有效算法，确定
T
是否有一个主元素。进一步，能找到一个线性时间算法吗？

注：实现的算法要求列出足够的实验结果。

 

1)  
基于分治法的线性时间求主元素算法

■   
算法思想

中位数：数列排序后位于最中间的那个数。如果一个数列有主元素
,
那么必然是其中位数。求一个数列有没有主元素，只要看中位数是不是主元素。

找中位数的方法
:
选择一个元素作为划分起点，然后用快速排序的方法将小于它的移动到左边，大于它的移动到右边。这样就将元素划分为两个部分。此时，划分元素所在位置为
k
。如果
k>n/2
，那么继续用同样的方法在左边部分找；如果
k<n/2
就在右边部分找；
k=n/2
就找到了中位元素。

根据快速排序的思想，可以在平均时间复杂度为
O(n)
的时间内找出一个数列的中位数。然后再用
O(n)
的时间检查它是否是主元素。

■   
算法实现

对应的
Java
程序在
MajorElement.java
中

----------------------------------------------------------------------------------------

判断是否是主元素的伪代码
:

master(A):

      len 
←
 length[A]

      median 
←
 randomizedSelect(A , 0 , n - 1 , n/2); 
▹
求中位数

      cnt 
←
 0

      
▹
计算中位数出现次数

      for i 
←
 0 to len – 1

        do if A[i] = median

               then cnt 
←
 cnt + 1

      if cnt > n/2

        then print "
主元素
:" +median + "
出现次数
:" + cnt

        else print "
无主元素
"

----------------------------------------------------------------------------------------

找一个序列中第
k
大的数伪代码

randomizedSelect(A , p , q , k):

      r 
←
 randomizedPartition (p , q)  
▹
找出划分元素
r

      if r = k

        then return A[r]

        else if r > k

                   then randomizedSelect(A , p , r – 1, k)

                   else randomizedSelect(A , r + 1 , q , k)

----------------------------------------------------------------------------------------

实现随机划分的伪代码
:

randomizedPartition(A , p , q ):
      rand 
←
 random(p , q)

      exchange A[rand] ↔A[q]

      return partition(p , q)

----------------------------------------------------------------------------------------

基于快速排序思想的划分伪代码
:

partition(A , p , q ):

      pivot 
←
 A[q]

      i 
←
 p – 1

      for j 
←
 p to q – 1

           do if A[j] <= pivot

                then i 
←
 i + 1

                            exchange A[i] ↔ A[j]

      exchange A[i + 1] ↔ A[q]

      return i + 1

----------------------------------------------------------------------------------------

■   
时间复杂度分析

master()
中求中位数可以在平均时间复杂度为
O(n)
的时间内完成
,
检查中位数是否是主元素耗时
O(n),
所以时间复杂度为
O(n)
。

 

2) 
无序关系时求主元素的
O(nlgn)
的算法

■   
算法思想

    
若
T 
中存在主元素，则将
T 
分为两部分后，
T 
的主元素也必为两部分中至少一部分的主元素，因此可用分治法。

将元素划分为两部分，递归地检查两部分有无主元素。算法如下：

a. 
若
T 
只含一个元素，则此元素就是主元素，返回此数。

      b. 
将
T 
分为两部分
T1 
和
T2
（二者元素个数相等或只差一个），分别递归调用此方法求其主元素
m1 
和
m2
。

      c. 
若
m1 
和
m2 
都存在且相等，则这个数就是
T 
的主元素，返回此数。

d. 
若
m1 
和
m2 
都存在且不等，则分别检查这两个数是否为
T 
的主元素，若有则返回此数，若无则返回空值。

e. 
若
m1 
和
m2 
只有一个存在，则检查这个数是否为
T 
的主元素，若是则返回此数，若否就返回空值。

f. 
若
m1 
和
m2 
都不存在，则
T 
无主元素，返回空值。

■   
算法实现

相应的
Java
程序在
MasterElement.java
中

-----------------------------------------------------------------------------------------

O(nlgn)
的算法伪代码
:

▹求
T[p..q]
中的主元素。返回主元素及其出现次数或空
(
表示无主元素
)

CheckMaster(T , p , q):

      if p ← q

           then return T[p] and 1

      len ← q – p + 1

      r ← p + len / 2

      a and numa ← CheckMaster(T , p , r – 1)

      b and numb ← CheckMaster(T , r , q)

     

      if a = NIL and b = NIL

           then return NIL

      if a = NIL and b 
≠
 NIL

           then return CheckAnotherPart(T , len , p , r – 1 , b , numb)

      if a 
≠
 NIL and b = NIL

           then return CheckAnotherPart(T , len , r , q , a , numa)

      if a 
≠
 NIL and b 
≠
 NIL

then if a = b

           then numa ← numa + numb

                  return a and numa

                      else re ← CheckAnotherPart(T , len , p , r – 1 , b ,numb)

                             if re 
≠
 NIL

                                 then return re

                                  else return CheckAnotherPart(T, len, r, q, a, numa)

-----------------------------------------------------------------------------------------

▹检查候选主元素是否是主元素

CheckAnotherPart(T , len , p , q , c , numc):

      numc ← CheckNum(T , p , q , c) + numc

      if num > len/2

           then return c and numc

           else return NIL

-----------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------

▹计算
T[p..q]
中
element
出现的次数

CheckNum( T , p , q , element):

      cnt ← 0

      for i ← p to q

           do if T[i] = element

                      then cnt ← cnt + 1

      return cnt

----------------------------------------------------------------------------------------

■   
时间复杂度分析

T(n)=2T(n/2)+n  

所以时间复杂度为
O(nlgn)

 

 

3)
无序关系时求主元素的
O(n)
算法

■   
算法思想

在一个集合中，删除两个不同的数，则集合的主元素保持不变。根据这个原理，可以很快求出主元素。

■   
算法实现

-------------------------------------------------------------------------------------

相应的
Java
程序在
MainElement.java
中

master(A):

      n ← length[A]

      count ← 1

      seed ← A[0]

      
▹
找候选主元素

      for i ← 1 to n – 1

           do if A[i] = seed

                   then count ← count + 1

                   else if count > 0

                              then count ← count – 1

                              else seed ← A[i]

      
▹
查找候选主元素是否是主元素

      count ← 0

      for i ← 0 to n – 1

        do if A[i] = seed

               then count ← count + 1

      if count > n/2

        then return seed and count

        else return NIL

-------------------------------------------------------------------------------------

■   
时间复杂度分析

时间复杂度为
O(n)

 

 

4)
算法测试

对前面三个求主元素算法，使用测试数据进行测试
:

测试数组

结果

0,0,1,1,0,8,1,1,1

主元素
:1
出现次数
:5

13,17,26,3,5,2,17,3

无主元素

1,2,3,4,5,6,7,8

无主元素

1,0,0,1,0,2,0

主元素
:0 
出现次数
:4

1,3,4,1,2,1,1,4,0,1,1,1

主元素
:1 
出现次数
:7

0,1,1

主元素
:1 
出现次数
:2

13,17,26,3,5,2,17,3,3,3,3,3,3

主元素
:3 
出现次数
:7

100,58

无主元素

597

主元素
:597 
出现次数
:1

6,1,2,2,2,3,5

无主元素

7,7,7,7,7,7

主元素
7  
出现次数
:6

5,9,45,96,77,28,13

无主元素