Q : 何为主元素：
设T[0:n-1]是n个元素的数组，对任意一个元素x，设S(x) = { i | T[i] = x }。当| S(x) | > n/2 时，称x为T的主元素。
算法实现：
1、快排 + 判断中位数
2、分治思想 (分解、递归实现)
3、线性算法 (主元素个数大于n/2)
方法一：针对有序数组，若存在主元素，则主元素肯定是中位数。
思路：先对数组进行快速排序，然后求解有序数组的中位数，若中位数个数>n/2 (或者判断中位数与第一个、最后一个元素的关系)，则中位数为主元素，否则不存在主元素。
分析：时间复杂度为O（nlogn）
代码实现：
#include <stdio.h>
#include <windows.h>
//利用快速排序的方法求中位数
void swap(int *a, int *b)
{
int temp = 0;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int *num, int start, int end)
{
int x = num[end];
int i = start-1;
int j;
for (j = start; j < end; j++) {
if (num[j] <= x) {
i = i + 1;
swap(&num[i], &num[j]);
}
}
swap(&num[i+1], &num[end]);
return i+1;
}
void quicksort(int *num, int start, int end)
{
if( start < end) {
int mid = partition(num, start, end);
quicksort(num, start, mid-1);
quicksort(num, mid+1, end);
}
}
int main()
{
int i,n;
int num[10];
int index;
printf("please input the number of a[]:");
scanf("%d",&n);
printf("please input a[]:\n");
for(i=0;i<n;i++)
scanf("%d",&num[i]);
quicksort(num, 0, n-1);
for (i = 0; i < n; i++) {
printf("%d\n", num[i]);
}
if(n%2 == 0)
index=n/2-1;
else
index = n/2; //奇数n/2偶数n/2-1
//中位数与第一个或者最后一个数相同，则为主元素
if (num[0] == num[index] || num[n-1] == num[index]) {
printf("main element exits: index = %d element = %d\n", index, num[index]);
}
else {
printf("main element not exits\n");
}
Sleep(10000000);
}
方法二：分治法
思路：若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 无主元素，返回空值。
分析：
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <windows.h>
typedef struct snode{
int data;
int count;
}*node;
int checkNum(int *num, int p, int q, int data)
{
int count = 0;
int i;
for (i = p-1; i < q; i++) {
if (num[i] == data) {
count++;
}
}
return count;
}
node checkAnotherPart(int *num, int len, int p, int q, node nodec)
{
nodec->count = checkNum(num, p, q, nodec->data) + nodec->count; //统计左右两部分元素出现个数
if (nodec->count > len/2) { //如若大于n/2,则符合要求返回，否则返回空
return nodec;
}
else {
return NULL;
}
}
node checkMaster(int *num, int p, int q)
{
node nodetmp = (node)malloc(sizeof(node));
node nodea = (node)malloc(sizeof(node));
node nodeb = (node)malloc(sizeof(node));
//递归结束条件
if (p == q) {
nodetmp->data = num[p-1];
nodetmp->count = 1;
return nodetmp;
}
int len = q - p + 1; //待检查数组长度(未必是从头开始:-p)
int mid = p + len / 2; //找数组中间位置(未必是从头开始:+p)
nodea = checkMaster(num, p, mid-1); //左半部分递归求解主元素
nodeb = checkMaster(num, mid, q); //右半部分递归求解主元素
if (nodea == NULL && nodeb == NULL) { //两部分都不存在主元素，则返回空
return NULL;
}
if (nodea == NULL && nodeb != NULL) { //左半部分存在，右半部分不存在时，检查左半部分主元素是否合格
return checkAnotherPart(num, len, p, mid-1, nodeb);
}
if (nodea != NULL && nodeb == NULL) { //左半部分不存在，右半部分存在时，检查右半部分主元素是否合格
return checkAnotherPart(num, len, mid, q, nodea);
}
if (nodea != NULL && nodeb != NULL) { //左右两部分都存在主元素
if (nodea->data == nodeb->data) { //左右两部分的主元素相同，直接返回
nodea->count = nodea->count + nodeb->count;
return nodea;
}
else { //左右两部分的主元素不同，分别检查其是否为原数组的主元素
node nodec = checkAnotherPart(num, len, p, mid-1, nodeb);
if (nodec != NULL) {
return nodec;
}
else {
return checkAnotherPart(num, len, mid, q, nodea);
}
}
}
}
int main()
{
int i,n,num[50];
printf("please input the number of num[]:");
scanf("%d",&n);
printf("please input num[]:\n");
for(i=0;i<n;i++)
scanf("%d",&num[i]);
node masterNode = checkMaster(num, 1, n);
if(masterNode == NULL)
printf("the main elemer not exist! \n");
else
printf("num = %d count = %d\n", masterNode->data, masterNode->count);
Sleep(10000000);
}
方法三：主元素个数 > n/2 ，所以主元素的个数减去其它元素的个数仍然大于0。
思路：假定a[0]为主元素mainE，主元素与其它元素的差值为dif，初值为1；然后进行比较，如果下一个元素与mainE相同，则++dif，否则--dif，若为0，则令后继元素为mainE，且dif置1。
分析：时间复杂度为：O(n) 线性
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
int mainElement(int a[], int n)
{
int mainE = a[0];
int dif = 1;
int i =1;
int count;
while(i < n)
{
if(a[i] == mainE)
{
++dif;
}
else
{
--dif;
if(!dif)
{
mainE = a[i+1];
++i;
dif = 1;
}
}
++i;
}
//统计mainE的个数，判断mainE是否是主元素
count = 0;
for (i = 0; i < n; i++) {
if (a[i] == mainE) {
count++;
}
}
if (count > n/2) {
return mainE;
}
return 0;
}
void main()
{
int a[10];
int i,n,mainE;
printf("please input the number of a[]:");
scanf("%d",&n);
printf("please input a[]:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mainE=mainElement(a,n);
if (mainE != 0)
printf("main element is %d\n", mainE);
else
printf("main element not exits\n");
Sleep(100000);
}
原文：http://www.cnblogs.com/xymqx/p/3616832.html