`
datoplay
  • 浏览: 1605503 次
文章分类
社区版块
存档分类
最新评论

编程之美系列之二——寻找出现频率超过一半的数

 
阅读更多

问题描述:

现在有一数组存放int型整数,数字有重复,且有一数字出现的频率超过了50%,请找出这个数字。

补充:主要考虑数据量很大的情况。

问题求解:

分析:

最直接的方法就是对数组中所有的数字排序,然后再扫描一遍,统计各个数字出现的次数,如果某个数字出现的次数超过一半,则输出这个数字。显然这个算法的时间复杂度是O(N * log2N + N)。

事实上,假如现在数组已经有序,那么数组中间的数字一定是这个要求的数字,所以根本不必扫描。此时算法的时间复杂度是O(N * log2N + 1)。那还能不能再简化一些呢?

我们看到,算法主要的消耗在排序这块,那能否跳过排序这个步骤呢?我们这样想,假如每次删除两个不同的数(不管包括不包括最高频数),那么,在剩下的数字里,原最高频数出现的频率一样超过了50%,不断重复这个过程,最后剩下的将全是同样的数字,即最高频数。此算法避免的排序,时间复杂度只为O(N)。

代码如下:

1 static int FindMostApperse(int[] num) 2 { 3 int candidate = 0; 4 int count = 0; 5 for (int i = 0; i < num.Length; i++) 6 { 7 if (count == 0) 8 { 9 candidate = num[i]; 10 count = 1; 11 } 12 else 13 { 14 if (candidate == num[i]) 15 count++; 16 else 17 count--; 18 } 19 } 20 return candidate; 21 }

这个算法体现了计算机科学中一种很普遍的思想,就是把一个问题转化为规模较小的若干个问题。分治、递归、贪心等都是基于这样的思想。转化的效率越高,转化之后问题的规模缩小的越快,则正题的时间复杂度越低。

扩展问题:

现在数组中没有出现频率一半的数字了,但有三个都超过了四分之一,找到他们。

分析:

与原问题一样,只要降低规模即可,每次去掉四个不相同的数字,一直重复,最后剩下的三个数字就是答案。

代码如下:

1 static int candiA = 0, candiB = 0, candiC = 0; 2 static void FindThreeMost(int[] num) 3 { 4 int countA = 0, countB = 0, countC = 0; 5 for (int i = 0; i < num.Length; i++) 6 { 7 if (countA == 0 || countB == 0 || countC == 0 ) 8 { 9 if (countA == 0) 10 { 11 if (countB != 0 && num[i] == candiB) 12 countB++; 13 else if (countC != 0 && num[i] == candiC) 14 countC++; 15 else 16 { 17 candiA = num[i]; 18 countA++; 19 } 20 } 21 else if (countB == 0) 22 { 23 if (countA != 0 && num[i] == candiA) 24 countA++; 25 else if (countC != 0 && num[i] == candiC) 26 countC++; 27 else 28 { 29 candiB = num[i]; 30 countB++; 31 } 32 } 33 else if (countC == 0) 34 { 35 if (countA != 0 && num[i] == candiA) 36 countA++; 37 else if (countB != 0 && num[i] == candiB) 38 countB++; 39 else 40 { 41 candiC = num[i]; 42 countC++; 43 } 44 } 45 } 46 47 else 48 { 49 if (num[i] == candiA) 50 countA++; 51 else if (num[i] == candiB) 52 countB++; 53 else if (num[i] == candiC) 54 countC++; 55 else 56 { 57 countA--; 58 countB--; 59 countC--; 60 } 61 } 62 } 63 }

此算法的时间复杂度仍为O(N),只是判断条件较多,欢迎大家拿出更简明的代码来讨论。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics