一、主元素問題
設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
|
無主元素
|