查找一個(gè)數(shù)組中超過(guò)一半的元素-創(chuàng)新互聯(lián)

程序1.0

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

    思想：現(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;
}

時(shí)間復(fù)雜度太大，不好

程序1.1 改進(jìn)

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

    利用快速排序，先在數(shù)組中隨機(jī)選擇一個(gè)數(shù)字，然后調(diào)整數(shù)字中數(shù)字的順序，使比選中的數(shù)字小數(shù)字都排在左邊，反之則在右邊，如果選中的數(shù)字下標(biāo)為n/2,那么這個(gè)數(shù)字就是數(shù)組的中位數(shù)，如果選中的數(shù)字下標(biāo)大于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ù)組特點(diǎn)找出O(N)算法

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

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

標(biāo)題名稱：查找一個(gè)數(shù)組中超過(guò)一半的元素-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://www.muchs.cn/article0/dodeoo.html

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

廣告

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