Majority Number I II III
一個尋衆數的問題。
多數投票算法 Boyer–Moore majority vote algorithm
- Majority Number I II III
- Majority Number
- Majority Number II
- Majority Number III
Majority Number
Leetcode:169. Majority Element
Lintcode:46. Majority Number
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Notice
You may assume that the array is non-empty and the majority number always exist in the array.
本題是一個求衆數問題，也是一個投票問題。需要找到數組中出現次數超過半數的元素。
本問題可以用貪心方法求解。由于本題中的衆數出現次數超過 ⌊n/2⌋ ⌊ n / 2 ⌋ 。
可以将本問題看做超過半數有效的投票問題。任取數組 A A 中一個元素AiAi将其看做目标衆數的候選值，其形成候選數組 B B 加入AiAi。
Ai A i 是否為結果的關鍵是，候選數組 B B 能否構成以AiAi為衆數的 A A 的子數組。
這時，考慮Aj，i≠jAj，i≠j與 Ai A i 的值。有兩種情況。
-
Ai=Aj A i = A j
此時将 Aj A j 加入數組 B B
-
Ai≠AjAi≠Aj
這時可以看出在數組 A A 中删去 Ai，AjAi，Aj并不影響數值 Ai，Aj A i ， A j 在數組中是衆數的可能性。
因為，衆數在數組中一定出現半數以上。
但删的是兩個不相同元素，假設其中一個是正确答案，則它與非衆數元素同時減少一個，答案元素仍超過半數。
如果，兩個都不是正确答案，删去這兩個元素。則正确答案占比仍超過半數。
綜上所述，這時抛棄 Aj A j 并删除 B B 中的一個 AiAi。
如果， 這時數組 B B 被删空了，就再從數組 AA的剩餘元素中選一個候選重複上述工作最後 B B 中剩餘元素即為最終答案。
我們可以看出數組 BB可以簡化為 Ai A i 的計數，添加為 + + ，删除為 −−。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = nums[]; //指定一個候選元素
int count = ; //數組B計數開始
for (int i = ; i < nums.size() ; i ++) {
if (candidate == nums[i])
//如果與候選元素相同，對數組B進行添加
count++;
else
//如果與候選元素不同，對數組B進行删去
count--;
if (count == ) {
//如果數組B已被删空則重新標明一個候選元素
candidate = nums[++i];
count++;
}
}
return candidate;
}
};
Majority Number II
Leetcode:229. Majority Element II
Lintcode:47. Majority Number II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Lintcode:47. Majority Number II Notice
There is only one majority number in the array.
本題是上一題的簡單拓展，衆數從超過半數變為超過 ⌊n/3⌋ ⌊ n / 3 ⌋ 。候選衆數變為兩個。這時需要對最終得到的候選衆數進行驗證。
注意到，LeetCode的題中衆數不唯一。
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
//有幾個候選衆數
int k = ;
//滿足是衆數的條件
int floor = nums.size() / ;
//建立候選衆數的容器
map<int , int> candidates;
//進行投票模拟
for (int i = ; i < nums.size() ; i ++) {
//如果實際候選數小于應有候選數，加入新的候選數
if (candidates.size() < k) {
//如果與已有候選數重複了，已有候選數進行計數添加。否則，添加候選數
if (candidates.find(nums[i]) != candidates.end())
candidates[nums[i]]++;
else
candidates[nums[i]] = ;
} else {
//如果實際候選數等于應有候選數
if (candidates.find(nums[i]) != candidates.end())
//如果與候選數中的其中一個相等，則未破壞子數組的特性，對候選數進行計數添加。
candidates[nums[i]]++;
else
//如果與候選數都不相等，則從nums中删去子數組 A_i，A_j，A_k
for (auto j = candidates.begin() ; j != candidates.end() ; ) {
j->second--;
if (j->second == )
j = candidates.erase(j);
else
j++;
}
}
}
//完成對候選數的驗證
for (auto c = candidates.begin() ; c != candidates.end() ; c ++) {
c->second = ;
}
for (int a : nums) {
if (candidates.find(a) != candidates.end())
candidates[a]++;
}
vector<int> res;
for (auto it : candidates) {
if (it.second > floor)
res.push_back(it.first);
}
return res;
}
};
Majority Number III
Lintcode:48. Majority Number III
Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.
Find it.
Notice
There is only one majority number in the array.
本題其實在在上一題中已經給出答案了。
class Solution {
public:
/*
* @param nums: A list of integers
* @param k: An integer
* @return: The majority number
*/
int majorityNumber(vector<int> &nums, int k) {
// write your code here
unordered_map<int , int> candidate;
int size = k - ;
for (int i = ; i < nums.size() ; i++) {
if (candidate.size() < size) {
if (candidate.find(nums[i]) == candidate.end()) {
candidate[nums[i]] = ;
} else {
candidate[nums[i]]++;
}
} else {
if (candidate.find(nums[i]) == candidate.end()) {
auto j = candidate.begin();
while (true) {
if (j == candidate.end()) {
break;
}
(j -> second)--;
if (j -> second == ) {
j = candidate.erase(j);
} else {
j++;
}
}
} else {
candidate[nums[i]]++;
}
}
}
for (auto i = candidate.begin() ; i != candidate.end() ; i++) {
i -> second = ;
}
int max = , res = ;
for (int i = ; i < nums.size() ; i++) {
candidate[nums[i]]++;
if (candidate[nums[i]] > max) {
max = candidate[nums[i]];
res = nums[i];
}
}
return res;
}
};
class Solution {
public:
/*
* @param nums: A list of integers
* @param k: An integer
* @return: The majority number
*/
int majorityNumber(vector<int> &nums, int k) {
// write your code here
//滿足是衆數的條件
int floor = nums.size() / k;
//建立候選衆數的容器
map<int , int> candidates;
//進行投票模拟
for (int i = ; i < nums.size() ; i ++) {
//如果實際候選數小于應有候選數，加入新的候選數
if (candidates.size() < k) {
//如果與已有候選數重複了，已有候選數進行計數添加。否則，添加候選數
if (candidates.find(nums[i]) != candidates.end())
candidates[nums[i]]++;
else
candidates[nums[i]] = ;
} else {
//如果實際候選數等于應有候選數
if (candidates.find(nums[i]) != candidates.end())
//如果與候選數中的其中一個相等，則未破壞子數組的特性，對候選數進行計數添加。
candidates[nums[i]]++;
else
//如果與候選數都不相等，則從nums中删去子數組 A_i，A_j，A_k
for (auto j = candidates.begin() ; j != candidates.end() ; ) {
j->second--;
if (j->second == )
j = candidates.erase(j);
else
j++;
}
}
}
//完成對候選數的驗證
for (auto c = candidates.begin() ; c != candidates.end() ; c ++) {
c->second = ;
}
for (int a : nums) {
if (candidates.find(a) != candidates.end())
candidates[a]++;
}
vector<int> res;
for (auto it : candidates) {
if (it.second > floor)
res.push_back(it.first);
}
return res[];
}
};
![Rewritethestars✨[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)