LeetCode169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. （Easy）
You may assume that the array is non-empty and the majority element always exist in the array.
分析：
抵消的思想，维护一个result和count,与result相同则count++，否则count--，到0时更新result的值，由于主元素个数较多，所有最后一定能留下。
代码：
1 class Solution { 2 public: 3 int majorityElement(vector<int>& nums) { 4 int result = 0; 5 int count = 0; 6 for (int i = 0; i < nums.size(); ++i) { 7 if (nums[i] == result && count != 0) { 8 count++; 9 } 10 else if (count == 0) { 11 result = nums[i]; 12 count = 1; 13 } 14 else { 15 count--; 16 } 17 } 18 return result; 19 } 20 };
LintCode47. Majority NumberII
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. （Medium）
Find it.
Notice : There is only one majority number in the array.
分析：
同majority number1的思路相似，维护两个result和count，相同则对相应count操作，不同则均减一；
注意最后剩下两个元素，并不一定count值大的就一定是出现次数多的（可能另一个参与抵消过多），所以需要重新遍历一遍，对这个两个数比较出现次数大小。
代码：
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: The majority number occurs more than 1/3. 6 */ 7 int majorityNumber(vector<int> nums) { 8 // write your code here 9 int candidate1 = 0, candidate2 = 0; 10 int count1 = 0, count2 = 0; 11 for (int i = 0; i < nums.size(); ++i) { 12 if (nums[i] == candidate1 && count1 != 0) { 13 count1++; 14 } 15 else if (nums[i] == candidate2 && count2 != 0) { 16 count2++; 17 } 18 else if (count1 == 0) { 19 candidate1 = nums[i]; 20 count1 = 1; 21 } 22 else if (count2 == 0) { 23 candidate2 = nums[i]; 24 count2 = 1; 25 } 26 else { 27 count1--; 28 count2--; 29 } 30 } 31 count1 = 0; 32 count2 = 0; 33 for (int i = 0; i < nums.size(); ++i) { 34 if (nums[i] == candidate1) { 35 count1++; 36 } 37 else if (nums[i] == candidate2) { 38 count2++; 39 } 40 } 41 return count1 > count2 ? candidate1 : candidate2; 42 } 43 };
LeetCode229. Majority Element 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.（Medium）
分析：
这个与lintcode中的majority number2基本相似，只是要求找到所有的大于n / 3次的元素（至多也就是两个）；
所以最后一步从比较两个canditate的count大小，变成将这两个count与 size() / 3比较。
代码：
1 class Solution { 2 public: 3 vector<int> majorityElement(vector<int>& nums) { 4 int candidate1 = 0, candidate2 = 0; 5 int count1 = 0, count2 = 0; 6 for (int i = 0; i < nums.size(); ++i) { 7 if (nums[i] == candidate1 && count1 != 0) { 8 count1++; 9 } 10 else if (nums[i] == candidate2 && count2 != 0) { 11 count2++; 12 } 13 else if (count1 == 0) { 14 candidate1 = nums[i]; 15 count1 = 1; 16 } 17 else if (count2 == 0) { 18 candidate2 = nums[i]; 19 count2 = 1; 20 } 21 else { 22 count1--; 23 count2--; 24 } 25 } 26 count1 = 0; 27 count2 = 0; 28 for (int i = 0; i < nums.size(); ++i) { 29 if (nums[i] == candidate1) { 30 count1++; 31 } 32 else if (nums[i] == candidate2) { 33 count2++; 34 } 35 } 36 vector<int> result; 37 if (count1 > nums.size() / 3) { 38 result.push_back(candidate1); 39 } 40 if (count2 > nums.size() / 3) { 41 result.push_back(candidate2); 42 } 43 return result; 44 45 } 46 };
LintCode48. 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. （Medium）
Find it.
Notice：There is only one majority number in the array.
分析：
从前一题的1/3变为1/k，道理还是一样，不过这次需要用一个hashmap来维护出现的次数，注意unordered_map插入删除相关操作的写法即可。
尤其hashmap元素个数等于k需要删除的时候，需要维护一个vector存key，如果用iterator边走边删除可能出现位置变化。
代码：
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @param k: As described 6 * @return: The majority number 7 */ 8 int majorityNumber(vector<int> nums, int k) { 9 // write your code here 10 unordered_map<int, int> hash; 11 for (int i = 0; i < nums.size(); ++i) { 12 if (hash.size() < k) { 13 hash[nums[i]]++; 14 } 15 else { 16 vector<int> eraseVec; 17 for (auto itr = hash.begin(); itr != hash.end(); ++itr) { 18 (itr -> second)--; 19 if (itr -> second == 0) { 20 eraseVec.push_back(itr -> first); 21 } 22 } 23 for (int i = 0; i < eraseVec.size(); ++i) { 24 hash.erase(eraseVec[i]); 25 } 26 hash[nums[i]]++; 27 } 28 } 29 for (auto& n : hash) { 30 n.second = 0; 31 } 32 for (int i = 0; i < nums.size(); ++i) { 33 if (hash.find(nums[i]) != hash.end()) { 34 hash[nums[i]]++; 35 if (hash[nums[i]] > nums.size() / k) { 36 return nums[i]; 37 } 38 } 39 } 40 return -1; 41 } 42 };