问题：
有整型数组a[1...n],如果整数x在数组a中出现的次数多于半数，则x称为多数元素。
方法：
计算每一个元素出现的次数,算法复杂度O(n2)(即n的平方).
归纳法分析此问题
观察结论5.1：在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新序列中还是多数元素。
例1：
1，2，2，3，2，2，3 显然2是多数元素
去除1，2，在2，3，2，2，3中2仍是多数元素
去除1，3，在2，3，2，2，3中2更是多数元素
例2：
1，3，2，3，2，2，3 显然没有多数元素
去除1，3，在2，3，2，2，3中2成了多数
故在观察结论“如果知道如何求解规模为n-1的问题，那么任务就化为如何把解法扩展到规模为n的问题”的支持下，能得到多数元素的候选者
算法：
1>寻找多数元素候选者的过程：
(1)计数器count置1，另c=A[1];
(2)从A[2]开始向后扫描，for j=2 to n
若a[j]与c相等，则count++;
若a[j]与c不等，则count—
若count==0,则对A[j+1...n]寻找多数元素候选者。
2>寻找候选者算法
Candidate(int A[],int m ,int n) {//寻找A[m...n]中多数元素候选者 c=A[m];
count=1; for(j=m+1;j<n&&count>0;j++) { if(A[j]==c) count++; else count--; } if(j==n) return c; else return canditate(j+1); //对A[j+1...n]寻找多数元素候选者。 }
3>判断数组有无多数元素算法
Majority(int A[],int n) { c = conditate(1); for (i=1; i<=n; i++) if (A[j] == c) count++; if ( count > n/2 ) return c; else return 0; //设数组A中元素均非0，返回0表示不存在多数元素 }