查找一個數(shù)組中超過一半的元素

程序1.0

    思想：現(xiàn)將數(shù)組排序，再找出元素

void Arraysort(int *a, int length)//冒泡O(n^2)
{

	for (size_t i = 0; i < length; i++)
	{
		for (size_t j = 1; j <length - 1 - i; j++)
		{
			if (a[j]>a[j + 1])
				swap(a[j], a[j + 1]);
		}
	}
}
int MorethanHalfNumber(int *a, int length)
{
	Arraysort(a, length);
	int count = 1;
	for (size_t i = 0; i < length-1; i++)
	{
		if (a[i] == a[i + 1])
		{
			count++;
			if (count == (length + 1) / 2)
				return a[i];
		}
		else
			count = 1;
	}
	return 0;
}

時間復雜度太大，不好

程序1.1 改進

    思想：如果數(shù)組中的一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，如果要排序，那么排序之后位于數(shù)組中間的數(shù)字一定就是那個出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)字

    利用快速排序，先在數(shù)組中隨機選擇一個數(shù)字，然后調(diào)整數(shù)字中數(shù)字的順序，使比選中的數(shù)字小數(shù)字都排在左邊，反之則在右邊，如果選中的數(shù)字下標為n/2,那么這個數(shù)字就是數(shù)組的中位數(shù)，如果選中的數(shù)字下標大于n/2則中位數(shù)在左邊，接著在它的左邊部分的數(shù)組中查找。。。利用遞歸完成

bool CheckMoreThanHalf(int *a, int length, int number)
{
	int count = 0;
	for (int i = 0; i < length; i++)
	{
		if (a[i] == number)
			count++;
	}
	
	if (count * 2 <= length)
		return false;
	return true;
}
int MorethanHalfNumber(int *a, int length)
{
	if ((a == NULL) || length <= 0)
		return 0;
	int mid = length >> 1;
	int start = 0;
	int end = length - 1;
	int index = Partition(a, length, start, end);//快排
	
	while (index != mid)
	{
		if (index > mid)
		{
			end = index - 1;
			index = Partition(a, length, start, end);
		}
		else
		{
			start = index + 1;
			index = Partition(a, length, start, end);
		}
	}
	int result = a[mid];
	if (!CheckMoreThanHalf(a, length, result))
		result = 0;
	return result;
}

程序2.0

    根據(jù)數(shù)組特點找出O(N)算法

    在遍歷數(shù)組的時候保存兩個值，一個數(shù)組的第一個數(shù)字，一個是次數(shù)，當遍歷到下一個數(shù)字時，若果下一個數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加1，如果下一個數(shù)字和之前保存的數(shù)字不同，次數(shù)減1，如果次數(shù)為0，我們保存下一個數(shù)字，并把次數(shù)設為1。由于要找的數(shù)字出現(xiàn)的次數(shù)一定比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設為1時的數(shù)字

bool CheckMoreThanHalf(int *a, int length, int number)
{
	int count = 0;
	for (int i = 0; i < length; i++)
	{
		if (a[i] == number)
			count++;
	}

	if (count * 2 <= length)
		return false;
	return true;
}
int MorethanHalfNumber(int *a, int length)
{
	if ((a == NULL) || length <= 0)
		return 0;

	int result = a[0];
	int count = 1;
	for (int i = 1; i < length; i++)
	{
		if (count == 0)
		{
			result = a[i];
			count = 1;
		}
		else if (a[i] == result)
			count++;
		else
			count--;
	}
	if (!CheckMoreThanHalf(a, length, result))
		result = 0;
	return result;
}