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

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

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

正片開始

概念

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

那我遍歷難道不香嗎?

在這里插入圖片描述

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

優(yōu)點

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

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

算法核心

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

在這里插入圖片描述

在這里插入圖片描述

實現(xiàn)

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

基于LeetCode真題實踐,先看一個初級栗子:

169. 多數(shù)元素
給定一個大小為 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 進行++,最后輸出 count 最大的。有點麻煩而且我忽視了一個最大的問題就是負數(shù)的存在,垮掉~

根據(jù)我們算法的思路,針對目標(biāo)數(shù)組 nums,首先創(chuàng)建一個變量來執(zhí)行計數(shù)器 count 再創(chuàng)建一個新數(shù)組 a 進行比對,因為始終是目標(biāo)數(shù)組的內(nèi)部元素比較,我可以直接把 nums 首元素賦給 a ,比較時從第二個元素開始和 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)在整一道硬菜,直接上升級版:
229. 求眾數(shù) II
給定一個大小為 n 的整數(shù)數(shù)組,找出其中所有出現(xiàn)超過 ⌊ n/3 ⌋ 次的元素。

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

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

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

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

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

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

    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語言算法金手指摩爾投票法手撕絕大多數(shù)問題的詳細內(nèi)容,更多關(guān)于C語言摩爾投票算法的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

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

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

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

    C語言時間處理實例分享

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