【剑指offer】37： 数字在排序数组中出现的次数
2021-05-30 11:00
标签：offer ber 时间复杂度 log col lse off nlogn 循环 题目描述： 解题思路： 看到题目，可直接暴力求解，循环数组，找出出现次数，但此时时间复杂度为O(n)。显然直接遍历，没有很好的利用题目中升序这个已知要求，我们只需要找到目标数字第一次和最后一次出现的位置，并且相减，可以直接得到次数，因此将思路转化为通过二分查找求第一个和最后一个k出现的位置（利用二分查找可以将时间复杂度直接降低为O(nlogn)） 代码实现 （C实现）： 【剑指offer】37： 数字在排序数组中出现的次数 标签：offer ber 时间复杂度 log col lse off nlogn 循环 原文地址：https://www.cnblogs.com/zhangshiliu/p/14753072.htmlint GetNumberOfK(int* data, int dataLen, int k ) {
// write code here
if (dataLen == 0) return 0;
int i = 0, j = dataLen - 1, right = 0, left = 0, mid;
while (i j)
{
mid = (i + j) / 2;
if (k >= data[mid]) i = mid + 1;
else j = mid - 1;
}
right = i;
i = 0;
j = dataLen - 1;
while (i j)
{
mid = (i + j) / 2;
if (k > data[mid]) i = mid + 1;
else j = mid - 1;
}
left = j;
return right - left - 1;
}