1 題目
Tango是微軟亞洲研究 院的一個試驗項目。研究院的員工和實習生們都很喜歡在Tango上面交流灌水把篓。傳說纫溃，Tango有一大“水王”，他不但喜歡發(fā)貼韧掩，還會回復其他ID發(fā)的每 個帖子紊浩。坊間風聞該“水王”發(fā)帖數(shù)目超過了帖子總數(shù)的一半。如果你有一個當前論壇上所有帖子（包括回帖）的列表疗锐，其中帖子作者的ID也在表中坊谁，你能快速找 出這個傳說中的Tango水王嗎？
2 分析
題目的實質是從一個數(shù)組中找到出現(xiàn)次數(shù)大于數(shù)組長度一半的元素滑臊。即[1,2,3,1,1,1]數(shù)組口芍，如何找到1
3 解法
書中列舉了幾種解法。
1）先排序雇卷，在統(tǒng)計各ID出現(xiàn)的次數(shù)鬓椭，超過總數(shù)一半的即為所求的。時間復雜度為O(nlogn+n)关划。
2）先排序小染，排序好后數(shù)組中n/2位置處的即為所需元素(前提是一定存在)，比如上面的排好序后為[1,1,1,1,2,3],7/2位置處的為1贮折。時間復雜度為O(n*logn)
3)假如注意到一個事實裤翩，假定a為數(shù)組中超過一半的元素，那么數(shù)組中除去兩個不相同的元素调榄，a依然是超過現(xiàn)在數(shù)組元素一半的元素岛都。這個可以使用簡單的數(shù)學證明下律姨。
4 代碼
我們使用一個candidate表示候選元素，使用一個nTimes表示候選元素的當前出現(xiàn)次數(shù)臼疫，遍歷數(shù)組择份，會有以下幾種情況：
- nTimes == 0 表示可能是遍歷的第一個元素，也可能是消除了若干對不同元素后的結果烫堤，但對應的處理很簡單荣赶，就是將當前的元素作為候選元素，同時nTimes 置為1
2)nTimes != 0 分為兩種情況:一種是候選元素和當前遍歷元素相等鸽斟，則說明遇到的是相同的元素拔创，不能刪除，需要nTimes自增1;另一種是不相同富蓄，則表示找到了兩個不同的元素剩燥，將nTimes自減1。
int[] a = {1,1,1,2,2,2,2,3,1,1,1};
int candidate = 0;
int nTimes = 0;
for(int i=0; i< a.length; i++){
if(nTimes == 0){
candidate = a[i];
nTimes = 1;
}else{
if(candidate == a[i]){
nTimes++;
}else{
nTimes--;
}
}
}
System.err.println(candidate);
5 擴展
隨著Tango的發(fā)展立倍，管理員發(fā)現(xiàn)灭红，“超級水王”沒有了。統(tǒng)計結果表明口注，有3個發(fā)帖很多的ID变擒，他們的發(fā)帖數(shù)目都超過了帖子總數(shù)目N的1/4。你能從發(fā)帖ID列表中快速找出他們的ID嗎寝志？
使用c1,c2,c3代表候選元素娇斑，使用t1,t2,t3表示對應的候選元素的當前出現(xiàn)次數(shù)，遍歷數(shù)組材部，當前遍歷元素為k,會有以下幾種情況:
- k 不在c1 c2 c3 里面毫缆，而且t1 t2 t3 有為0的，那么就說明候選元素還沒有選完乐导，需要將對應t為0的c置為k,同時對應的t置為1
2)k 不在c1 c2 c3 里面苦丁，且t1 t2 t3 均不為0，說明遇到了四個不同的元素兽叮，t1 t2 t3 均自減1
3)k 在c1 c2 c3 里面芬骄，則對應的t自增1
前提是數(shù)組中的元素不會為-1
public static void main(String[] args){
int[] b = {1,2,3,4,1,2,3,4,1,2,3,4,3,2,1};
int[] c = {-1,-1,-1};
int[] t = {0,0,0};
for(int i = 0; i < b.length; i++){
int whichCandidate = getCandidate(b[i], c);
int which = getFreeStore(t);
if(whichCandidate == -1 && which != -1){
c[which] = b[i];
t[which] = 1;
}else if(whichCandidate == -1 && which == -1){
t[0]--;
t[1]--;
t[2]--;
}else if(whichCandidate != -1){
t[whichCandidate]++;
}
}
System.err.println(c[0]+" " + c[1] +" " + c[2]);
}
public static int getCandidate(int c,int[] candidate){
for(int i = 0; i < candidate.length; i++){
if(c == candidate[i]){
return i;
}
}
return -1;
}
public static int getFreeStore(int[] t){
for(int i = 0; i < t.length;i++){
if(t[i] == 0){
return i;
}
}
return -1;
}
