2013 年

找出数组中个数超过数组长度一半的数（主元素）

int partion(int A[],int low,int high){
	int pivot=A[low];
	while(low<high){
		while(low<high && A[high]>=pivot) high--;
		A[low]=A[high];
		while(low<high && A[low]<=pivot) low++;
		A[high]=A[low];
	}
	A[low]=pivot;
	return low;
}
 
void q_sort(int A[],int low,int high){
	while(low<high){
		int pivot=partion(A,low,high);
		q_sort(A,low,pivot-1);
		q_sort(A,pivot+1,high);
	}
}
 
int fing_main_element(int A[],int n){
	int sorted_A[]=q_sort(A,0,n-1);
	int count=1;
	int current=A[0];
	for(int i=1;i<n;i++){//遍历数组
		if(A[i]==current){//如果当前元素和上一元素相同
			count++;//则计数+1
		}else{
			current=A[i];//否则从该位置开始重新计数
			count=1;
		}
		if(count>n/2){
			return current;
		}
	}
	return -1;
}