一、主元素问题

    设 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

无主元素