欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言算法金手指摩爾投票法手撕絕大多數(shù)問(wèn)題

 更新時(shí)間:2022年02月14日 10:06:30   作者:?jiǎn)虇碳业凝堼? 
這篇文章主要為大家介紹了C語(yǔ)言算法之金手指摩爾投票法手撕絕大多數(shù)問(wèn)題的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助

正片開(kāi)始

概念

嘛是摩爾投票法?
簡(jiǎn)單來(lái)說(shuō)就是投票法,算法解決的問(wèn)題是如何在任意多的候選人,選出獲得票數(shù)最多的那個(gè)。常見(jiàn)的算法是掃描一遍選票,也就是遍歷,對(duì)每個(gè)候選人進(jìn)行統(tǒng)計(jì)的選票進(jìn)行統(tǒng)計(jì)。

那我遍歷難道不香嗎?

在這里插入圖片描述

這里就要講一下投票法的過(guò)人之處

優(yōu)點(diǎn)

當(dāng)執(zhí)行有序情況時(shí),只要找到中位數(shù),然后檢查中位數(shù)的個(gè)數(shù)是否超過(guò)選票的一半即可。但是當(dāng)對(duì)象的數(shù)目不定時(shí),統(tǒng)計(jì)選票可能會(huì)執(zhí)行較長(zhǎng)時(shí)間,相比原來(lái)的時(shí)間復(fù)雜度 O(n) ,可能需運(yùn)行 O(n^2) 的時(shí)間。

針對(duì)無(wú)序且對(duì)象不定的情況,摩爾投票法應(yīng)運(yùn)而生。

算法核心

摩爾投票法的關(guān)鍵就是抵消和計(jì)數(shù),抵消過(guò)程類似于是在進(jìn)行投票,然后計(jì)數(shù)我們可以腦補(bǔ)一個(gè)情形:當(dāng)三人中的一人得票數(shù)遠(yuǎn)超其他兩人時(shí),我們就可以進(jìn)行等量對(duì)消,消完還有票的自然就是得票數(shù)最多的那個(gè),模擬如下:(ppt手殘勿噴)

在這里插入圖片描述

在這里插入圖片描述

實(shí)現(xiàn)

基本思路就是由一個(gè)計(jì)數(shù)器維護(hù),在進(jìn)行比較過(guò)程中,不同票消掉,相同票保留,如果消的沒(méi)有了就直接放進(jìn)去然后繼續(xù)上述過(guò)程,直到維護(hù)對(duì)象只剩一個(gè),就是我們要找的最大得票者(眾數(shù))。

基于LeetCode真題實(shí)踐,先看一個(gè)初級(jí)栗子:

169. 多數(shù)元素
給定一個(gè)大小為 n 的數(shù)組,找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ⌊ n/2 ⌋ 的元素。你可以假設(shè)數(shù)組是非空的,并且給定的數(shù)組總是存在多數(shù)元素。

示例:
輸入:[2,2,1,1,1,2,2]
輸出:2

來(lái)源:力扣(LeetCode)

我最初的思路是哈希思想,qsort 之后用最大的元素 malloc 一塊新的空間,桶排后用 count 進(jìn)行++,最后輸出 count 最大的。有點(diǎn)麻煩而且我忽視了一個(gè)最大的問(wèn)題就是負(fù)數(shù)的存在,垮掉~(yú)

根據(jù)我們算法的思路,針對(duì)目標(biāo)數(shù)組 nums,首先創(chuàng)建一個(gè)變量來(lái)執(zhí)行計(jì)數(shù)器 count 再創(chuàng)建一個(gè)新數(shù)組 a 進(jìn)行比對(duì),因?yàn)槭冀K是目標(biāo)數(shù)組的內(nèi)部元素比較,我可以直接把 nums 首元素賦給 a ,比較時(shí)從第二個(gè)元素開(kāi)始和 a 比較,如果相同,count ++;不同消掉,count --;沒(méi)有了就往里拿。

int majorityElement(int* nums, int numsSize){
    int count = 1;
    int a = nums[0];
    for(int i =1;i<numsSize;i++)
    {
        if(nums[i]==a)
        {
            count++;
        }
        else
        {
            count--;
        }
        if(count==0)
        {
        a = nums[i+1];
        }
    }
    return a;
}

格局抬高

現(xiàn)在整一道硬菜,直接上升級(jí)版:
229. 求眾數(shù) II
給定一個(gè)大小為 n 的整數(shù)數(shù)組,找出其中所有出現(xiàn)超過(guò) ⌊ n/3 ⌋ 次的元素。

示例 :
輸入:[1,1,1,3,3,2,2,2]
輸出:[1,2]

還是那句話,題目越少眼淚越飽,短小精悍的題 nnd 硬磨了我一個(gè)下午,桶是肯定桶不了的,哈希又沒(méi)學(xué),不做吧心里太不舒服,這里就又有我摩爾投票法的一席之地了

注意,題目給的是超過(guò) n/3 次的元素,這很重要,其實(shí)就是在暗示我們結(jié)果至多只會(huì)有三種情況:沒(méi)有眾數(shù)或者一個(gè)眾數(shù)或者兩個(gè)眾數(shù);但是頭疼的是咱之前的摩爾投票法好像行不通,因?yàn)檫@里對(duì)象不定,如果出現(xiàn)了兩個(gè)眾數(shù)我的 “ 票 ” 該怎么投?

將之前的格局打開(kāi),我們可以將所有數(shù)字分為兩類,> n/3 的元素 和 <= n/3 的元素,其中大于 n/3 的元素最多只有兩個(gè)。因此可以設(shè)置三個(gè)變量,進(jìn)行相對(duì)抵消,這里我們不妨再引入一個(gè)容器 b,再用一個(gè)新的計(jì)數(shù)器 count2 來(lái)進(jìn)行維護(hù),當(dāng)三個(gè)元素相同時(shí),count++,不同就抵消,為 0 就用把這個(gè)數(shù)放進(jìn)去,基本思想和上面是差不多的:

    int a = nums[0];
	int b = nums[1];
	int count1, count2 = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (a == nums[i])
		{
			count1++;
			continue;
		}
		else if (b == nums[i])
		{
			count2++;
			continue;
		}
		else
		{
			count1--;
			count2--;
		}
		if (count1 < 0)
		{
			a = nums[i];
			count2++;
			count1 = 1;
		}
		if (count2 < 0)
		{
			b = nums[i];
			count1++;
			count2 = 1;
		}
	}

還沒(méi)完,因?yàn)閿?shù)組可能存在一個(gè)眾數(shù)或者沒(méi)有眾數(shù)的情況,我們還需要再次遍歷來(lái)統(tǒng)計(jì)我們篩選的眾數(shù)的出現(xiàn)次數(shù)是否符合題目要求的大于n/3 以及排除數(shù)組為空或單項(xiàng)的情況:

    count1 = 0;
	count2 = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (a == nums[i])
		{
			count1++;
		}
	    else if (b == nums[i])
		{
			count2++;
		}
	}
		if (numsSize <= 1)
	{
		*returnSize = numsSize;
		return nums;
	}

最后直接依次放入一塊新的空間再返回即可,全部代碼如下:

int* majorityElement(int* nums, int numsSize, int* returnSize) {
	if (numsSize <= 1)
	{
		*returnSize = numsSize;
		return nums;
	}
	int a = nums[0];
	int b = nums[1];
	int count1, count2 = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (a == nums[i])
		{
			count1++;
			continue;
		}
		else if (b == nums[i])
		{
			count2++;
			continue;
		}
		else
		{
			count1--;
			count2--;
		}
		if (count1 < 0)
		{
			a = nums[i];
			count2++;
			count1 = 1;
		}
		if (count2 < 0)
		{
			b = nums[i];
			count1++;
			count2 = 1;
		}

	}
	count1 = 0;
	count2 = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (a == nums[i])
		{
			count1++;
		}
	    else if (b == nums[i])
		{
			count2++;
		}
	}
	int* c = (int*)malloc(sizeof(int) * 2);
    *returnSize = 0;
	if (count1 > numsSize / 3)
	{
		c[(*returnSize)++] = a;
	}
	if (count2 > numsSize / 3)
	{
		c[(*returnSize)++] = b;
	}
	return c;
}

家人們明白了嗎,那今天就到這里,摸了。

以上就是C語(yǔ)言算法金手指摩爾投票法手撕絕大多數(shù)問(wèn)題的詳細(xì)內(nèi)容,更多關(guān)于C語(yǔ)言摩爾投票算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C?C++輸入輸出基礎(chǔ)教程示例詳解

    C?C++輸入輸出基礎(chǔ)教程示例詳解

    當(dāng)我們?cè)诰W(wǎng)站做題的時(shí)候經(jīng)常會(huì)遇到各種要求的輸入輸出,而且會(huì)有時(shí)間超限等多個(gè)問(wèn)題,這時(shí)我們就要優(yōu)化我們的輸入輸出或者規(guī)范我們的輸入輸出格式,下面介紹C和C++中的輸入輸出問(wèn)題,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2023-11-11
  • C語(yǔ)言時(shí)間處理實(shí)例分享

    C語(yǔ)言時(shí)間處理實(shí)例分享

    這篇文章主要介紹了C語(yǔ)言時(shí)間處理實(shí)例分享的相關(guān)資料,需要的朋友可以參考下
    2015-07-07
  • 最新評(píng)論