Majority Element

原題鏈接Majority Element

給定一個(gè)數(shù)組，元素個(gè)數(shù)為n，找出出現(xiàn)次數(shù)大于n/2的那個(gè)元素

摩爾投票法思想

每次從數(shù)組中選擇兩個(gè)不相等的元素進(jìn)行相互抵消(刪除)，最后剩下的一個(gè)元素或幾個(gè)相同的元素就是出現(xiàn)次數(shù)大于n/2的元素

代碼如下

class Solution { public:int majorityElement(vector<int>& nums) {int major = 0, count = 0;for(auto& n : nums){if(major == n) ++count;else if(count == 0) major = n, count = 1;else --count;}return major;} };

---

Majority Element II

原題鏈接Majority Element II

找到所有出現(xiàn)次數(shù)大于n/3的元素，顯然最多只能有兩個(gè)，同樣利用摩爾投票法

代碼如下

class Solution { public:vector<int> majorityElement(vector<int>& nums) {int y = 0, z = 0, cy = 0, cz = 0;for(auto& x : nums){if(y == x) ++cy;else if(z == x) ++cz;else if(cy == 0) y = x, cy = 1;else if(cz == 0) z = x, cz = 1;else --cy, --cz;}cy = cz = 0;for(auto& x : nums){if(y == x) ++cy;else if(z == x) ++cz;}vector<int> res;if(cy > nums.size() / 3) res.push_back(y);if(cz > nums.size() / 3) res.push_back(z);return res;} };

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----摩尔投票法寻找给定数组中出现个数大于n/2或n/3的元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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