因为是有序的,所以用二分查找更快。找到比k小的第一个数作为左边界,找到比k大的第一个数作为右边界,右-左即k的个数。
按普通找某个数的位置来找,只是把int 改为double, 找k-0.5和k+0.5
int position(int* data, int n, double k){
int left = 0, right = n-1, mid = 0;
while(left <= right){
mid = (left + right)/2;
if(data[mid] < k)
left = mid + 1;
else if(data[mid] > k)
right = mid - 1;
else
return mid;
}
return left;
}
int GetNumberOfK(int* data, int dataLen, int k ) {
return position(data, dataLen, k+0.5) - position(data, dataLen, k-0.5);
}

京公网安备 11010502036488号