上海网站建设方案策划,创造网站,海外注册域名的网站,博物馆装修厂家题解 | #数字在升序数组中出现的次数#
JZ3数字在升序数组中出现的次数
描述
给定一个长度为 n 的非降序数组和一个非负数整数 k #xff0c;要求统计 k 在数组中出现的次数
数据范围#xff1a;0≤n≤1000,0≤k≤100#xff0c;数组中每个元素的值满足 0≤val≤100 要求…题解 | #数字在升序数组中出现的次数#
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.hint 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;
}
