剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution { public: int majorityElement(vector<int>& nums) { map<int, int> mp; for (auto it = nums.begin(); it < nums.end(); it++) { if (mp.end() != mp.find(*it)) { mp[*it]++; } else { mp.insert(pair<int, int>(*it, 1)); } } int countMax = 0, maxNumber = 0; for (auto & iterator : mp) { if (iterator.second > countMax) { countMax = iterator.second; maxNumber = iterator.first; } } return maxNumber; } };比较神奇的一种算法：摩尔投票法
class Solution { public: int majorityElement(vector<int>& nums) { int count = 0, res; size_t size = nums.size(); for (int i = 0; i < size; ++i) { if (count == 0) { res = nums[i]; count++; } else { count += (nums[i] == res) ? +1 : -1; } } return res; } };