题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
1 class Solution { 2 public: 3 int MoreThanHalfNum_Solution(vector<int> numbers) { 4 int len = numbers.size(); 5 if (len == 0) 6 return 0; 7 int MAX = len / 2; 8 map<int,int> mm; 9 for (int i = 0; i < len ; ++i) 10 { 11 if (mm.count(numbers[i]) == 0) 12 { 13 mm[numbers[i]] = 1; 14 } 15 else 16 { 17 ++ mm[numbers[i]]; 18 } 19 } 20 for (map<int,int>::iterator it = mm.begin() ; it != mm.end() ; ++ it) 21 { 22 if (it->second > MAX) 23 { 24 return it->first; 25 } 26 } 27 return 0; 28 } 29 };