本文共 1148 字，大约阅读时间需要 3 分钟。

时间复杂度：O(n*logn)

将数组A划分成两个数组A1和A2，各含有A中的一半元素。考虑以下的问题：如果知道了A1和A2中各自的主元素，是否会对找出A中的主元素有所帮助？ → 分治法

/*找数组的主元素(主元素的重复次数超过数组大小的一半)。先将数组划分成两个数组A1和A2，找它们各自的主元素。*/#include 
   
    #include 
    
     using namespace std;int Partition(int data[], int head, int tail);int main(){	int data[10] = { 5, 5, 3, 4, 4, 4, 4, 5, 5 };	int data[10] = { 5, 5, 5, 3, 4, 4, 5, 5, 4 };	if (Partition(data, 0, 9) != INT_MAX)	{		cout << Partition(data, 0, 9) << endl;	}	else	{		cout << "该数组没有主元素" << endl;	}	return 0;}int Partition(int data[], int head, int tail){	//划分到子数组只有一个元素，返回该元素	if (head == tail)	{		return data[head];	}	int mid = (head + tail) / 2;	int num1 = Partition(data, head, mid);	int num2 = Partition(data, mid + 1, tail);	if (num1 == num2)	{		//两个子数组的主元素不存在，则原数组也不存在主元素		//两个子数组的主元素存在相等，则原数组的主元素一定为子数组的主元素		return num1;	}	else	{		//子数组的主元素都存在但不相等，检查它们在原数组中是否是主元素		int cnt1 = 0, cnt2 = 0;		for (int i = head; i <= tail; ++i)		{			if (data[i] == num1)			{				++cnt1;			}			if (data[i] == num2)			{				++cnt2;			}		}		if (cnt1 > (tail - head + 1) / 2)		{			return num1;		}		else if (cnt2 > (tail - head + 1) / 2)		{			return num2;		}		else		{			return INT_MAX;		}	}}
    
   

转载地址：http://bttai.baihongyu.com/