主元素算法

1.算法描述（算法分析2.26）

大小为N的数组A,其主元素是一个出现超过N/2次的元素（从而这样的元素最多只有一个）。例如，数组

3,3,4,2,4,4,2,4,4只有一个主元素4； 3,3,4,2,4,4,2,4没有主元素

求出主元素，没有请指出

 

2.书中列出了一种算法，暂且叫递归法，这可以自己看书，其复杂度也只有O(n)

 

下面介绍两种其他的方法。

在网上还有其他一些方法：http://wintys.blog.51cto.com/425414/100688/

 

3.方法一

 

思想就是利用主元素的个数是>N/2的这一性质,复杂度O(n)

*首先，随机选取一个作为主元素

*其次，依次遍历数组，遍历中遇到相同的count++,否则count--

*如果<=0时在换主元素

*最后，剩下的就做为主元素的人选

*当然选出来的不一定就是主元素，还要检测，如果检测成功，那必定就是主元素，否则就没有

 

 

int getMain(int* a, int length){
	int count =0;
	int seed = a[0];
	for(int i=0; i<length; i++){
		if(a[i]==seed) count++;
		else if(count>0) count--;
		else seed = a[i];
	}
	return seed;
}

 这个方法很简单，简洁明了

 

4.方法二

 

方法二：利用快速排序，最后选取N/2处的元素作为主元素,复杂度为快速排序的复杂度

*当然选出来的不一定就是主元素，还要检测，如果检测成功，那必定就是主元素，否则就没有

 

int getMain1(int* a, int length){
	quickSort(a, 0, length-1);
	return a[length/2];
}

 就是利用了快速排序

 

5.全部代码

 

/**
	*2.26找超过n/2次出现的主元素
	**/
#include <iostream>
using namespace std;


//检查是否是主元素
bool check(int* a, int length, int n){
	int count = 0;
	for(int i=0; i<length; i++){
		if(a[i]==n) count++;
	}
	if(count>length/2) return true;
	return false;
}

void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}

//一次划分 
int partition(int *a, int first, int end){
	int i=first;                        //初始化
	int j=end;
	while(i < j){
		while(i<j && a[i] <= a[j]) j--;
		if(i<j){
			swap(a[i], a[j]);
			i++;
		}
		while(i<j && a[i] <= a[j]) i++;
		if(i<j){
			swap(a[i], a[j]);
			j--;
		}
	}
	return i;
}

//快速排序
void quickSort(int* a, int first, int end){
	if(first < end){
		int pivot=partition(a, first, end);  //一次划分
    quickSort(a, first, pivot-1);//递归地对左侧子序列进行快速排序
    quickSort(a, pivot+1, end);  //递归地对右侧子序列进行快速排序
	}
}


/**
	*方法一：思想就是利用主元素的个数是>N/2的这一性质,复杂度O(n)
	*首先，随机选取一个作为主元素
	*其次，依次遍历数组，遍历中遇到相同的count++,否则count--
	*如果<=0时在换主元素
	*最后，剩下的就做为主元素的人选
	*当然选出来的不一定就是主元素，还要检测，如果检测成功，那必定就是主元素，否则就没有
	**/
int getMain(int* a, int length){
	int count =0;
	int seed = a[0];
	for(int i=0; i<length; i++){
		if(a[i]==seed) count++;
		else if(count>0) count--;
		else seed = a[i];
	}
	return seed;
}


/**
	*方法二：利用快速排序，最后选取N/2处的元素作为主元素,复杂度为快速排序的复杂度
	*当然选出来的不一定就是主元素，还要检测，如果检测成功，那必定就是主元素，否则就没有
	**/
int getMain1(int* a, int length){
	quickSort(a, 0, length-1);
	return a[length/2];
}

int main(){
	int a[] = {6,1,6,3,6,6,4,2,6};
	//动态获取数组的长度
	int length = sizeof(a)/sizeof(int);
//	int v = getMain(a, length);
	int v = getMain1(a, length);
	cout<<"length:"<<length<<",seed:"<<v<<endl;
	if(check(a, length, v)){
		cout<<"主元素是:"<<v<<endl;
	}else{
		cout<<"没找到主元素!"<<endl;
	}
	return 0;
}