查找排序数组中数字出现的次数

       例如输入数组{1,2,3,3,3,3,4,5,6}中查找3出现的次数。最为简单的方法就是从头遍历这个数组，统计3出现的次数，可是这样没有利用这是一个排序了的数组这个条件，时间复杂度O(n)。另一种方法就是利用二分查找的算法找到一个3，然后分别向左和向右查找第一个和最后一个3所在的位置，这样虽然比第一种方法效率提高了，但是当最坏的情况时，即数组中所有的元素都是3时，这样时间复杂度依然为O(0.5n) == O(n)。因此有必要继续提高效率。

      既然要找到3出现的第一个位置和最后一个位置，就可以多次利用二分查找算法，例如找第一个3出现的位置，当查找到某个3时，判断它的左边元素是不是3，如果是，说明第一个为3的元素在左边区间，这样就缩小了查找区间，继续在左区间二分查找即可。因此这样时间复杂度就变为了O(logn) 。

int GetFirstK(int* array, int length, int k, int start, int end)
{
if( start > end )
return -1;
int middleIndex = ( start + end ) / 2;
int middleData = array[middleIndex];
if( middleData == k )
{
/*如果是第一个k,则直接返回*/
if( ( middleIndex > 0 ) && ( array[middleIndex-1] != k ) || middleIndex == 0 )
return middleIndex;
else
end = middleIndex - 1;
}
else if( k < middleData )
end = middleIndex - 1;
else
start = middleIndex + 1;
return GetFirstK( array, length, k, start, end );
}
int GetLastK(int* array, int length, int k, int start, int end)
{
if( start > end )
return -1;
int middleIndex = ( start + end ) / 2;
int middleData = array[middleIndex];
if( middleData == k )
{
/*如果是最后一个k,则直接返回*/
if( ( middleIndex < length-1 ) && ( array[middleIndex +1] != k) || middleIndex == length-1 )
return middleIndex;
else
start = middleIndex + 1;
}
else if( k < middleData )
end = middleIndex - 1;
else
start = middleIndex + 1;
return GetLastK( array, length, k, start, end);
}
int GetNumberOfK(int* array, int length, int k)
{
int number = 0;
if( array != NULL && length > 0 )
{
int first = GetFirstK( array, length, k, 0, length-1);
int last = GetLastK( array, length, k, 0, length-1 );
if( first > -1 && last > -1 )
number = last - first + 1;
}
return number;
}

最后

以上就是忧伤樱桃为你收集整理的查找排序数组中数字出现的次数的全部内容，希望文章能够帮你解决查找排序数组中数字出现的次数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。