問題引入：
給定一個大小為 n 的陣列，找到其中的多數元素，多數元素是指在陣列中出現次數 大于 ? n/2 ? 的元素，
我們很輕松的想到暴力求解的方法：
定義兩個指標i和j，i記錄該位置的數字，j向后遍歷
每遇到相等的數字就將計數器+1
如果計數器大于了n/2，就停止，并回傳此時的i
但這種演算法的時間復雜度較高，為O(n2)，顯然達不到題目的要求
所以，為了將這道題的時間復雜度降到O(n)，我們可以使用摩爾投票法
演算法簡介
摩爾投票法，是一個方便求眾數的演算法，其演算法核心思想是：
- 將陣列中第一個元素記錄下來，并將計數器置為1
- 往后遍歷陣列，如果遇到相等的元素，計數器加一
- 如果遇到不相同的元素，計數器減一
- 減到0后，將記錄的元素更新為當前指標的后一個元素，并更新計數器為1
- 遍歷完陣列后最后存盤的數字，就是我們要求的眾數
形象解釋
我們可以想象有一個總統競選，超過半數的當選總統
設有1,2,3三位總統競選，選民將自己支持的總統的序號寫在自己的牌子上
但不同的選民都互相看不順眼，不順眼的一對全部出去打架去了
這是出去打架后剩下的結果
可以觀察到：
剩下的數字，絕對是那個超過了總數一半數字的
所以我們能輕易求出這個超過一半選票的總統是1
這就是我們理解這個演算法的基礎
代碼實作
int majorityElement(int* nums, int numsSize){
int count=0;
int ret=0;
for(int i=0;i<numsSize;i++)
{
if(count==0)//更新數字
{
ret=nums[i];
count=1;
}
else
{
if(ret==nums[i])//如果相等，計數器加一
{
count++;
}
else
{
count--;//不相等就減一
}
}
}
return ret;//最后記錄的數字就是我們要求的眾數
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/335460.html
標籤：其他