数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
题意：首先数组是个已经排列的有序递增序列！统计一个数出现的次数，相当于在有序的序列里插入一个数，那么我只要确定插入的位置，利用快排的思想，也可以说是二分，如果在数组中找到k，那么左右拓展边界就可以确定，，该数在数组中出现的次数了。
一些特殊情况可以特判！比如k小于数组最小数，或者大于数组最大数；
class Solution {public:int GetNumberOfK(vector<int> data ,int k) {if(data.size()<=0) return 0;if(data[0]>k || data[data.size()-1]<k) return 0;int left=0;int right=data.size()-1;int x=0,y=0,len=right;bool bo=false;while(left<=right){int mid=(left+right)/2;if(data[mid]==k){bo=true;x=y=mid;while(y+1<=len && data[y+1]==k) ++y;while(x-1>=0 && data[x-1]==k) –x;break;}if(data[mid]>k){right=mid-1;}else if(data[mid]<k){left=mid+1;}}//printf("x=%d\ty=%d\n",x,y);if(bo) return y-x+1;else return 0;}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
回味起来却有久久不会退去的余香。
