程序1.0

成都創(chuàng)新互聯(lián)公司專注于企業(yè)成都全網營銷、網站重做改版、涇川網站定制設計、自適應品牌網站建設、H5頁面制作、商城系統(tǒng)網站開發(fā)、集團公司官網建設、成都外貿網站制作、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為涇川等各大城市提供網站開發(fā)制作服務。

    思想：現(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ù)字，然后調整數(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

    根據數(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;
}

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

標題名稱：查找一個數(shù)組中超過一半的元素-創(chuàng)新互聯(lián)
標題網址：http://www.js-pz168.com/article0/dodeoo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、營銷型網站建設、電子商務、網站設計公司、品牌網站建設、關鍵詞優(yōu)化

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)