408专项数据结构2013

题目：

分析：题目大意就是要找到一段连续相等且最后一个元素在数组后半截。

理解错了，还以为是连续的序列，m是坐标。实际就是求最多的元素，要求超过n/2.

思路一：暴力循环

思考：暴力双循环，但时间复杂度有点低，拿分可以拿9分。

int find_main(int a[],int n)
{
	int cnt;
	for(int i=0;i<n;i++)
	{
		cnt=1;
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]==a[j]) cnt++;
		}
		if(cnt>n/2) return 1;
	}
	return -1;
}

时间复杂度：O（n^2）,O(1)

思路二：排序

思考：对序列进行排序后，判断一段连续序列的长度是否超过n/2;用快排注意平均时间复杂度是O(nlogn)，归并才是真正的最坏O(nlogn)。但我不确定实际书写的时候能否用sort函数代替加快速率，如果不能，我大概率不会选择去手写一个快排。

时间复杂度：O（nlogn）,O(1)

思路三：抵消法

思考：个人理解就是军团打架，一v一剩下来的肯定是最多军团的人。正式一点说应该是摩尔投票法。没必要纠结名字，思想很简单。

int find_main2(int a[],int n)
{
	int fight=a[0],cnt=1;
	for(int i=1;i<n;i++)//找站在最后或站的最多人的团 
	{
		if(a[i]==fight) cnt++;
		else cnt--;
		if(cnt==0) fight=a[i],cnt=1;
	}
	cnt=0;
	for(int i=0;i<n;i++)//判断该团是否超过总数的一半人 
		if(a[i]==fight) cnt++;
	if(cnt>n/2) return 1;
	return -1;
}

时间复杂度：O（n）,O(1)