将数组A划分为两个数组A1和A2 ,各含有A的一半元素或一半多一个.若A中含有主元素x,则A1和A2中至少有一个数组含有主元素x,对A1和A2递归地计算有无主元素,若A只含有一个元素,则A的主元素就是这个元素,否则计算出A1和A2的主元素x1和x2:
若x1和x2都不存在,则A不存在主元素
若x1和x2有一个存在，则检查这个元素是否为A的主元素
若x1和x2都存在且不相等，则分别检查这个元素是否为A的主元素
若x1和x2都存在且相等，则这个元素就是A的，主元素
package org.xiu68.ch02.ex2;
public class Ex2_23a {
public static void main(String[] args) {
//n个元素的数组，相同元素个数大于一半称为主元素，元素之间不能比较大小，可以作相等比较
//以O(nlogn)时间确定数组是否含有主元素
//String[] strs=new String[MAX_LENGTH];
String[] strs2=new String[]{"aa","bb","cc","aa","aa","bb","cc","aa","aa"};
Sal s2=countPrime(strs2,0,strs2.length-1);
if(s2!=null)
System.out.println(s2);
}
//求数组中p到q间的主元素
public static Sal countPrime(String[] strArr,int p,int q){
//如果只有一个元素，这个元素就是主元素
if(p==q)
return new Sal(strArr[p],1);
int partLength=q-p+1; //元素个数
int middle=p+partLength/2; //元素中间位置
Sal first=countPrime(strArr,p,middle-1); //前一部分的主元素
Sal second=countPrime(strArr,middle,q); //后一部分的主元素
//前半部分和后半部分都没有主元素，则没有主元素
if(first==null && second==null)
return null;
//后半部分有主元素，则遍历数组确定后半部分的主元素是否为前后两部分的主元素
if(first==null && second!=null)
return countPart(strArr,partLength, p, middle-1, second.getStr(), second.getCount());
//前半部分有主元素，则遍历数组确定前半部分的主元素是否为前后两部分的主元素
if(first!=null && second==null)
return countPart(strArr,partLength, middle, q, first.getStr(), first.getCount());
//前后两部分都有主元素
if(first!=null && second!=null){
//若主元素相同,则这个元素就是整个部分的主元素
if(first.getStr().equals(second.getStr()))
return new Sal(first.getStr(),first.getCount()+second.getCount());
else{
//主元素不相同，则分别计算前后两部分的主元素是否为整个部分的主元素
Sal temp=countPart(strArr,partLength, p, middle-1, second.getStr(), second.getCount());
if(temp!=null)
return temp;
return countPart(strArr,partLength, middle, q, first.getStr(), first.getCount());
}
}
return null;
}
//计算某个元素是否为某一部分的主元素
public static Sal countPart(String[] strArr,int partLength,int p,int q,String k,int firstNum){
int lastNum=0;
for(int i=p;i<=q;i++){
if(strArr[i].equals(k))
lastNum++;
}
int finalNum=firstNum+lastNum;
if(finalNum>(partLength/2))
return new Sal(k,finalNum);
return null;
}
}
class Sal{
private String str; //主元素
private int count; //主元素个数
public Sal(){}
public Sal(String str, int count) {
super();
this.str = str;
this.count = count;
}
public String getStr() {
return str;
}
public void setStr(String str) {
this.str = str;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public String toString(){
return "主元素:"+this.getStr()+",个数"+this.getCount();
}
}