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

时间:2021-01-04 11:07:16

剑指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 }