数字在升序数组中出现的次数
这道题可以用遍历数组和二分查找来处理
1.题目描述
2.题目分析
题目中有一个关键信息，非降序数组，我们可以使用if语句来处理这个问题
if(numsLen==0){ return 0; } else if (nums[numsLen-1]<k||nums[0]>k) { return 0; }
2.1遍历数组方法
int GetNumberOfK(int* nums, int numsLen, int k ) { int count = 0; if(numsLen==0){ return 0; } else if (nums[numsLen-1]<k||nums[0]>k) { return 0; } for(int i=0;i<numsLen;i++){ if (k==nums[i]) { count++; } } return count; }
遍历数组的方法应该是最直接有效的，当k出现一次，则count自增，最终返回count的值即是k出现的次数
2.2二分查找方法
二分查找是我们经常使用的一种算法，他的逻辑是
在升序或者降序且无重复元素的数组中，比较目标值和数组中间值的方法，每次缩小一半的搜索范围，相比遍历可以加快计算的速度
假设：目标值为下标为4的数值，给定一个大小为10的数组，我们给定他的下界left=0，上界right=numsLen-1，中间下标mid=（left+right）/2
二分查找：
- 判断目标值target是否等于num[mid]；
- 如果相等则返回mid
如果不相等则判断target与num[mid]的大小关系；
- target>num[mid]；则说明目标值在后半部分，因为mid与目标值不相等，那么left就变成mid+1；
- target<num[mid]；则说明目标值在前半部分，因为mid与目标值不相等，那么right就变成mid-1；
每次缩小范围后都需要继续执行上述步骤，我们可以使用一个while循环，当left<right的时候循环，直到找到目标值对应的下标，返回下标；或者没有目标值对应的下标，返回-1；
2.3代码示例
按照这个思路，我们编写一下我们的代码
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* nums, int numsLen, int k ){ return position(nums,numsLen, k+0.5) - position(nums,numsLen, k-0.5); }
找到比k小的第一个数作为左边界，找到比k大的第一个数作为右边界，右-左即k的个数
按普通找某个数的位置来找，只是把int 改为double, 找k-0.5和k+0.5
