剑指offer中有这道题,何海涛博客:数组中出现次数超过一半的数字
题目:给定一个数组,数组中有一个数字出现的次数超过数组长度的一半,找出这个数字。
思路:
- 先排序,再遍历,统计次数,时间O(N * lgN)。
- 哈希表:统计每个元素次数,当数据分散时消耗空间大。
- 快排的Partition,判断pviot是不是中位数。时间复杂度不好确定。
- 一个很妙的答案,设置一个计数器cnt,一个变量var;当cnt为0时,var设置为当前数字,把cnt置1;如果当前数字和上一个相同,则cnt加1,否则减1;最后如果存在要查找的数,一定是var保存的数。
代码:
1 int moreThanHalfNum(int num[], int n) 2 { 3 if(num == NULL || n < 1) 4 return 0; 5
6 int var = num[0]; 7 int cnt = 1; 8 for(int i = 1; i < n; ++i) 9 { 10 if(cnt == 0) 11 { 12 var = num[i]; 13 cnt = 1; 14 } 15 else if(num[i] == var) 16 { 17 ++cnt; 18 } 19 else
20 { 21 --cnt; 22 } 23 } 24
25 //检查找到的数是否正确,因为数组中可能不存在超过一半的数
26 cnt = 0; 27 for(int i = 0; i < n; ++i) 28 { 29 if(num[i] == var) 30 { 31 ++cnt; 32 } 33 } 34
35 if(cnt << 1 <= n) 36 var = 0; 37
38 return var; 39 }