正片開始

概念

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

那我遍歷難道不香嗎？

這里就要講一下投票法的過人之處

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

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

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

算法核心

摩爾投票法的關(guān)鍵就是抵消和計(jì)數(shù)，抵消過程類似于是在進(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)行比較過程中，不同票消掉，相同票保留，如果消的沒有了就直接放進(jìn)去然后繼續(xù)上述過程，直到維護(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

來源：力扣（LeetCode）

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

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

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)超過 ⌊ n/3 ⌋ 次的元素。

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

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

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

將之前的格局打開，我們可以將所有數(shù)字分為兩類，> n/3 的元素 和 <= n/3 的元素,其中大于 n/3 的元素最多只有兩個(gè)。因此可以設(shè)置三個(gè)變量，進(jìn)行相對(duì)抵消，這里我們不妨再引入一個(gè)容器 b，再用一個(gè)新的計(jì)數(shù)器 count2 來進(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;
		}
	}

還沒完，因?yàn)閿?shù)組可能存在一個(gè)眾數(shù)或者沒有眾數(shù)的情況，我們還需要再次遍歷來統(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ù)問題的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言摩爾投票算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論