大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 数字在排序数组中出现的次数

数字在排序数组中出现的次数

关键词:次数数字排序  阅读(684) 赞(12)

[摘要]本文是对数字在排序数组中出现的次数的讲解,对学习C++编程技术有所帮助,与大家分享。

统计一个数字在排序数组中出现的次数。例如输入{2,2,2,2,2,3,5,5}和数字2,输出5.

常规的顺序扫描法时间复杂度是O(n),可以进一步优化。用二分查找的方法进行查找可以把时间复杂度降为O(logn)。

代码如下:

 int GetFirstK(int* data, int length, int k, int start, int end)//用二分查找法找到第一个K的位置
 {
     if (start > end)
     {
         return -1 ;
     }
     int MidIndex = (start + end) / 2 ;
     int MidData = data[MidIndex];
     if (MidData == k)
     {
         if (MidIndex == 0 || MidIndex > 0 && data[MidIndex - 1] != k)//在首位或是不在首位且前一位不是K时
         {
             return MidIndex ;
         }
         else //不是第一个K时
         {
             end = MidIndex - 1 ;
         }
     }
     else if ( MidData > k)
     {
         end = MidIndex - 1 ;
     }
     else
     {
         start = MidIndex + 1 ;
     }
     return GetFirstK(data, length, k, start, end) ;
 }
 
 int GetLastK(int* data, int length, int k, int start, int end)//用二分查找法找到最后一个K的位置
 {
     if (start > end)
     {
         return -1 ;
     }
     int MidIndex = (start + end) / 2 ;
     int MidData = data[MidIndex];
     if (MidData == k)
     {
         if (MidIndex == length - 1 || MidIndex < length - 1 && data[MidIndex + 1] != k)//在末位或是不在末位且后一位不是K时
         {
             return MidIndex ;
         }
         else  //不是最后一个K时
         {
             start = MidIndex + 1 ;
         }
     }
     else if ( MidData > k)
     {
         end = MidIndex - 1 ;
     }
     else
     {
         start = MidIndex + 1 ;
         
     }
 
     return GetLastK(data, length, k, start, end) ;
 
 }
 int GetNumberOfK(int* data, int length, int k)//得到K的个数
 {
     if (!data || length < 1)
     {
         return 0 ;
     }
     int first = GetFirstK(data, length, k, 0, length - 1);
     int last = GetLastK(data, length, k, 0, length - 1);
     int number = 0 ;
     if (first != -1 && last != -1)
     {
         number = last - first + 1 ;
     }
     return number ;
 }


相关评论