思路:
最簡(jiǎn)單的思路是hush的定址法統(tǒng)計(jì)各個(gè)數(shù)字的個(gè)數(shù)。最后遍歷hush輸出數(shù)量最多的。
這顯然是非常的耗費(fèi)空間。因?yàn)轭}目中并沒(méi)有說(shuō)明各個(gè)數(shù)字的大小的取值范圍。
那么我們換一種方法: 用棧來(lái)解決問(wèn)題
例如:

由上圖我們可以得出以下的三個(gè)結(jié)論:

• 棧為空入棧
• 棧頂元素和與元素相等入棧
• 棧定和元素不相等出棧

其實(shí)用通俗易懂的話來(lái)說(shuō)就是挨個(gè)比較不同的抵消了。那么留下來(lái)的就是數(shù)量最多的。

注意:
題目中有一個(gè)條件是多數(shù)元素的個(gè)數(shù)大于數(shù)組的1/2，正是因?yàn)檫@樣才可以用這種方法。
如果不是那么該方法不能使用。
例如: 2 2 1 3 5 最后留下的是 5 這顯然是不正確的。
代碼如下:

int majorityElement(int* nums, int numsSize){int *stack=(int *)malloc(sizeof(int)*numsSize);int top=-1;for(int i=0;i<numsSize;i++){if(top==-1)//棧里沒(méi)有元素，入棧{stack[++top]=nums[i];continue;}if(nums[i]==stack[top])//相等入棧{stack[++top]=nums[i];continue;}top--;//不相等，出棧}return stack[0]; }

這時(shí)候的時(shí)間復(fù)雜度是O(n),空間復(fù)雜度也是O(n)。
其實(shí)通過(guò)分析你會(huì)發(fā)現(xiàn)棧其實(shí)不用那么大，我們完全可以用一個(gè)元素來(lái)統(tǒng)計(jì)棧頂元素，
一個(gè)元素來(lái)統(tǒng)計(jì)個(gè)數(shù)。
代碼如下:

int majorityElement(int* nums, int numsSize){int count=0;int number=0;for(int i=0;i<numsSize;i++){if(count==0)//棧為空入棧{number=nums[i];count++;continue;}else if(number==nums[i]){count++;}else//出棧count--;}return number; }

上面這種方法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(0).

上面的總結(jié)是根據(jù)這個(gè)視頻總結(jié)的:
https://www.bilibili.com/video/BV13s41197my

總結(jié)

以上是生活随笔為你收集整理的力扣:169. 多数元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。