数组中出现次数超过一半的数字

1、利用快速排序，排好序中间的值就是出现次数超过一半的数字

注意：判断数组是否有效，判断出现次数频率是否超过数组大小的一半

#include<iostream>
#include<assert.h>
#include<stdlib.h>

#include <utility> 
using namespace std;

bool g_Invalid=true;
int PartSort(int* a, int left, int right) //快排排序
{
	assert(a);
	int key = a[right];
	int begin = left;
	int end = right-1;
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}

		while (begin < end && a[end] >= key)
		{
			--end;
		}

		if (begin < end)
		{
			swap(a[begin], a[end]);
		}
	}

	if (key < a[end])
	{
		swap(a[right], a[end]);
	}

	return end;
}

// []
void QuickSort(int* a, int left, int right)  
{
	assert(a);
	if(left < right)
	{
		int mid = PartSort(a, left, right);
		QuickSort(a, left, mid-1);
		QuickSort(a, mid+1, right);
	}
}
int PartSortNew(int* a,int left,int right)  //快速排序第二种方法
{
	assert(a);
	int prev=left-1;
	int cur=left;
	while(cur<right)
	{
		if(a[cur]<a[right]&&++prev!=cur)
		{
			swap(a[cur],a[prev]);
		}
		++cur;
	}
	swap(a[right],a[++prev]);  //找到最终排好序的a[right]的位置，++prev左边比a[right]小，右边比a[right]大
	return prev;
}
void QuickSortNew(int* a, int left, int right)  
{
	assert(a);
	if(left < right)
	{
		int mid = PartSortNew(a, left, right);
		QuickSortNew(a, left, mid-1);
		QuickSortNew(a, mid+1, right);
	}
}
bool Check(int* a,int len,int num)
{
	if(a==NULL||len<=0)
	{
		g_Invalid=false;
		return g_Invalid;
	}
	int times=0;
	for(int i=0;i<len;i++)
	{
		if(a[i]==num)
		{
			times++;
		}
	}
	if(times*2 <=len )
	{
		g_Invalid=false;
	}
	return g_Invalid;
}
void PrintArray(int* a,int len)
{
	for(int i=0;i<len;i++)
	{
		cout<<a[i]<<"-";
	}
}
void TestQuickSort()
{
	int array[10] = {2, 5, 4, 9, 3, 6, 8, 5, 1, 5};
	int a[]={1,2,3,2,2,2,5,4,2};
	//PrintArray(array, 10);
	/*QuickSort(array, 0, 9);
	PrintArray(array, 10);*/
	QuickSortNew(a,0,8);
	PrintArray(a,9);
	cout<<endl;
	cout<<"出现次数超过一半的数："<<a[9/2]<<endl;
	cout<<"数组是否有效："<<Check(a,9,2)<<endl;
}
int main()
{
	TestQuickSort();
	system("pause");
	return 0;
}

2、解法二：

在遍历数组时保存两个值，一个是数组中的数字，一个是次数，遍历到下一个数字的时候，如果和我们之前保存的数字相同，次数加1；如果和我们之前保存的数字不同，次数减1；如果次数为0，需要保存下一个值，并把次数置为1,。最后次数为1的肯定是我们要找的数。

//
#include<iostream>
using namespace std;
bool Check(int* a,int len)
{
	if(a==NULL||len<=0)
	{
		return false;
	}
	return true;
}
bool FinCheck(int* a,int len,int num)
{
	int times=0;
	for(int i=0;i<len;i++)
	{
		if(a[i]==num)
		{
			times++;
		}
	}
	if(times*2<=len)
	{
		return false;
	}
	return true;
}
void MoreThanHalfNum(int* a,int len)
{
	if(!Check(a,len))
	{
		return;
	}
	int result=a[0];
	int times=1;
	for(int i=1;i<len;i++)
	{
		if(times==0)
		{
			result=a[i];
			times=1;
		}
		else if(a[i]==result)
		{
			times++;
		}
		else
		{
			times--;
		}

	}
	if(FinCheck(a,len,result))
		cout<<"出现次数超过一半的数："<<result<<endl;
}
int main()
{
	int a[]={1,2,3,2,2,2,5,4,2};
	int len=sizeof(a)/sizeof(a[0]);
	MoreThanHalfNum(a,len);
	system("pause");
	return 0;

}

结果：