算法题——数组中出现次数超过一半的数字

剑指offer中有这道题，何海涛博客：数组中出现次数超过一半的数字

 

题目：给定一个数组，数组中有一个数字出现的次数超过数组长度的一半，找出这个数字。

 

思路：

• 先排序，再遍历，统计次数，时间O(N * lgN)。

• 哈希表：统计每个元素次数，当数据分散时消耗空间大。

• 快排的Partition，判断pviot是不是中位数。时间复杂度不好确定。

• 一个很妙的答案，设置一个计数器cnt，一个变量var；当cnt为0时，var设置为当前数字，把cnt置1；如果当前数字和上一个相同，则cnt加1，否则减1；最后如果存在要查找的数，一定是var保存的数。

 

代码：

int moreThanHalfNum(int num[], int n)  2 {  3     if(num == NULL || n < 1)  4         return 0;  5     
    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
 { 21             --cnt; 22  } 23  } 24 
    //检查找到的数是否正确，因为数组中可能不存在超过一半的数
    cnt = 0; 27     for(int i = 0; i < n; ++i) 28  { 29         if(num[i] == var) 30  { 31             ++cnt; 32  } 33  } 34 
    if(cnt << 1 <= n) 36         var = 0; 37 
    return var; 39 }