一、主元素問題
設(shè)T[0..n-1]是n個元素的數(shù)組。對任一元素x，設(shè)S(x)={i|T[i]=x}。當(dāng)|S(x)|>n/2時，稱x為T的主元素。
1) 如果T中元素存在序關(guān)系，按分治策略設(shè)計并實現(xiàn)一個線性時間算法，確定T[0..n-1]是否有一個主元素。
2) 若T中元素不存在序關(guān)系，只能測試任意兩個元素是否相等，試設(shè)計并實現(xiàn)一個O(nlogn)有效算法，確定T是否有一個主元素。進一步，能找到一個線性時間算法嗎？
注：實現(xiàn)的算法要求列出足夠的實驗結(jié)果。
1) 基于分治法的線性時間求主元素算法
■
算法思想
中位數(shù)：數(shù)列排序后位于最中間的那個數(shù)。如果一個數(shù)列有主元素,那么必然是其中位數(shù)。求一個數(shù)列有沒有主元素，只要看中位數(shù)是不是主元素。
找中位數(shù)的方法:選擇一個元素作為劃分起點，然后用快速排序的方法將小于它的移動到左邊，大于它的移動到右邊。這樣就將元素劃分為兩個部分。此時，劃分元素所在位置為k。如果k>n/2，那么繼續(xù)用同樣的方法在左邊部分找；如果k<n/2就在右邊部分找；k=n/2就找到了中位元素。
根據(jù)快速排序的思想，可以在平均時間復(fù)雜度為O(n)的時間內(nèi)找出一個數(shù)列的中位數(shù)。然后再用O(n)的時間檢查它是否是主元素。
■
算法實現(xiàn)
對應(yīng)的Java程序在MajorElement.java中
----------------------------------------------------------------------------------------
判斷是否是主元素的偽代碼:
master(A):
len
← length[A]
median
←
randomizedSelect(A , 0 , n - 1 , n/2); ?求中位數(shù)
cnt
← 0
?計算中位數(shù)出現(xiàn)次數(shù)
for
i ← 0 to len – 1
do if A[i] = median
then cnt ← cnt + 1
if
cnt > n/2
then print "主元素:" +median + "出現(xiàn)次數(shù):"
+ cnt
else print "無主元素"
----------------------------------------------------------------------------------------
找一個序列中第k大的數(shù)偽代碼
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)
----------------------------------------------------------------------------------------
實現(xiàn)隨機劃分的偽代碼:
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
----------------------------------------------------------------------------------------
■
時間復(fù)雜度分析
master()中求中位數(shù)可以在平均時間復(fù)雜度為O(n)的時間內(nèi)完成,檢查中位數(shù)是否是主元素耗時O(n),所以時間復(fù)雜度為O(n)。
2) 無序關(guān)系時求主元素的O(nlgn)的算法
■
算法思想
若T 中存在主元素，則將T 分為兩部分后，T 的主元素也必為兩部分中至少一部分的主元素，因此可用分治法。
將元素劃分為兩部分，遞歸地檢查兩部分有無主元素。算法如下：
a. 若T 只含一個元素，則此元素就是主元素，返回此數(shù)。
b. 將T 分為兩部分T1 和T2（二者元素個數(shù)相等或只差一個），分別遞歸調(diào)用此方法求其主元素m1 和m2。
c. 若m1 和m2 都存在且相等，則這個數(shù)就是T 的主元素，返回此數(shù)。
d. 若m1 和m2 都存在且不等，則分別檢查這兩個數(shù)是否為T 的主元素，若有則返回此數(shù)，若無則返回空值。
e. 若m1 和m2 只有一個存在，則檢查這個數(shù)是否為T 的主元素，若是則返回此數(shù)，若否就返回空值。
f. 若m1 和m2 都不存在，則T 無主元素，返回空值。
■
算法實現(xiàn)
相應(yīng)的Java程序在MasterElement.java中
-----------------------------------------------------------------------------------------
O(nlgn)的算法偽代碼:
?求T[p..q]中的主元素。返回主元素及其出現(xiàn)次數(shù)或空(表示無主元素)
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出現(xiàn)的次數(shù)
CheckNum( T , p , q , element):
cnt
← 0
for
i ← p to q
do
if T[i] = element
then
cnt ← cnt + 1
return
cnt
----------------------------------------------------------------------------------------
■
時間復(fù)雜度分析
T(n)=2T(n/2)+n
所以時間復(fù)雜度為O(nlgn)
3)無序關(guān)系時求主元素的O(n)算法
■
算法思想
在一個集合中，刪除兩個不同的數(shù)，則集合的主元素保持不變。根據(jù)這個原理，可以很快求出主元素。
■
算法實現(xiàn)
-------------------------------------------------------------------------------------
相應(yīng)的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
-------------------------------------------------------------------------------------
■
時間復(fù)雜度分析
時間復(fù)雜度為O(n)
4)算法測試
對前面三個求主元素算法，使用測試數(shù)據(jù)進行測試:
|
測試數(shù)組
|
結(jié)果
|
|
0,0,1,1,0,8,1,1,1
|
主元素:1出現(xiàn)次數(shù):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 出現(xiàn)次數(shù):4
|
|
1,3,4,1,2,1,1,4,0,1,1,1
|
主元素:1 出現(xiàn)次數(shù):7
|
|
0,1,1
|
主元素:1 出現(xiàn)次數(shù):2
|
|
13,17,26,3,5,2,17,3,3,3,3,3,3
|
主元素:3 出現(xiàn)次數(shù):7
|
|
100,58
|
無主元素
|
|
597
|
主元素:597 出現(xiàn)次數(shù):1
|
|
6,1,2,2,2,3,5
|
無主元素
|
|
7,7,7,7,7,7
|
主元素7 出現(xiàn)次數(shù):6
|
|
5,9,45,96,77,28,13
|
無主元素
|