【回眸】剑指offer（二）解题思路

题解 | #数字在升序数组中出现的次数#

JZ3数字在升序数组中出现的次数

描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

输入：

[1,2,3,3,3,3,4,5],3

返回值：

4

 做题思路

函数名为GetNumberOfK。函数接受三个参数：data是一个整型数组指针，dataLen是数组的长度，k是要查找的目标值。 函数的目标是统计数组中目标值k出现的次数，并返回该次数。函数的实现思路如下： 初始化变量mid、start和end，分别表示当前搜索范围的中间位置、起始位置和结束位置。 初始化变量left和right，分别表示目标值k的左边界和右边界。 使用二分查找的思路，在数组中找到目标值k的任意一个位置。 如果data[mid]大于k，将end更新为mid。 如果data[mid]小于k，将start更新为mid。 如果data[mid]等于k，表示找到目标值，将left和right初始化为mid。 在找到目标值的位置后，分别向左和向右遍历数组，找到目标值k的左边界和右边界。 当data[left]等于k时，向左移动left。 当data[right]等于k时，向右移动right。 返回右边界right减去左边界left再减去1，即为目标值k在数组中出现的次数。

C语言代码 

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @param k int整型* @return int整型*/
#include <stdio.h>
#include <stdlib.h>int GetNumberOfK(int* data, int dataLen,int k ) {  //先找到目标target值的任意一个位置，再分别往左往右找int mid = 0;int start = 0;int end = dataLen - 1;int left = 0 ;int right = 1;for (int i = start; i <= end; i++) {mid = (start + end) / 2;if (data[mid] > k) {end = mid;}if (data[mid] < k) {start = mid;}if (data[mid] ==k) {                                         //找到值的时候break;left = mid;right = mid;printf("mid=%d\n", mid);while (data[left] == k) {left--;}while (data[right] == k) {right++;}printf("left=%d right=%d\n", left, right);break;}}return right - left - 1;
}