题目：统计一个数字在排序数组中出现的次数。例如，输入排序数组{1,2,3,3,3,3,4,5}和数字3
由于3在这个数组中出现了4次，因此输出4.
该问题主要考察应聘者的知识迁移能力，主要是将二分查找的思想和方法迁移过来。所以这样的题
是面试官青睐的一种题型。
看到排序数组就要联想到二分查找。
-----------------------------------------------------------------------------------------------------------------------
算法分析：
解法一：
该解法是最直观的解法，可以先使用二分查找先找到这个元素，然后分别向左和向右遍历，把左右
相同的元素的个数都计算出来。
该方法很直观，当算法的效率太低。
解法二：
可以将问题转化下：
使用二分查找的拓展，当查找的元素有重复的时，找到元素的第一个和最后一个。
这样将可以计算出该元素有多少个重复的了。
详细可参考：
http://blog.chinaunix.net/space.php?uid=27033491&do=blog&id=3308974
-----------------------------------------------------------------------------------------------------------------------
算法的实现：
完整代码见：
count_k.c.rar
------------------------------------------------------------------------------------------------------------------------
阅读(2065) | 评论(0) | 转发(0) |
