查找一個數組中超過一半的元素

程序1.0

    思想：現將數組排序，再找出元素

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 改進

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

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

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

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

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

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;
}