数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。因为数字2在数组中出现了5次,超过数组长度的一半,所以输出2。若是不存在则输出0。数组
思路:code
1.map统计次数,时间复杂度O(n),空间换时间io
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { map <int, int> m; int maxCnt = 0; for(int i = 0; i < numbers.size(); ++i){ maxCnt = ++m[numbers[i]]; if(maxCnt > numbers.size() / 2)//超过数组长度一半的数只会存在一个 return numbers[i]; } return 0; } };
2.若是一个元素出现次数超过一半,那么他的次数必定大于其余元素出现次数之和。所以咱们每次保留两个值,第一值为数组中的一个数,另一个值为次数。初始时数为数组中第一个元素,次数为1,每次遍历时,若次数为0,说明当前元素与保留数不一样,把当前数赋值给保留数,次数置为1,若当前元素与保留数相同,则次数加1,若不一样则次数减一。最后再遍历一遍数组查看保留数是否出现次数超过一半。时间复杂度O(n)。class
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int n = numbers.size(); if(n < 1) return 0; int res = numbers[0]; int times = 1;//出现次数 for(int i = 1; i < n; ++i){ if(times == 0){ res = numbers[i]; times = 1; } else if(res == numbers[i]){ ++times; } else{ --times; } } times = 0; for(int i = 0; i < n; ++i){ if(numbers[i] == res) ++times; } if(times * 2 <= n) return 0; return res; } };