轉(zhuǎn)載請注明出處：http://blog.csdn.net/ns_code/article/details/27364557

題目描寫敘述：

統(tǒng)計(jì)一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

輸入：

每一個測試案例包括兩行：

第一行有1個整數(shù)n，表示數(shù)組的大小。1<=n <= 10^6。

第二行有n個整數(shù)，表示數(shù)組元素，每一個元素均為int。

第三行有1個整數(shù)m，表示接下來有m次查詢。1<=m<=10^3。

以下有m行，每行有一個整數(shù)k，表示要查詢的數(shù)。

輸出：

相應(yīng)每一個測試案例，有m行輸出，每行1整數(shù)，表示數(shù)組中該數(shù)字出現(xiàn)的次數(shù)。

例子輸入：

81 2 3 3 3 3 4 513

例子輸出：

4

? ? 我做這道題，是先用二分查找找到該數(shù)字，而后再遍歷其前后同樣的數(shù)字，統(tǒng)計(jì)次數(shù)。這種做法的平均時間復(fù)雜度為O（logn），最壞情況下為O(n),劍指offer上給的思路是兩次用二分查找分別找到該數(shù)字第一次和最后一次出現(xiàn)的位置，這種時間復(fù)雜度平均和最壞都是O（logn），稍好些》

? ? 以下貼上我依照自己思路寫的代碼：

#include<stdio.h> #include<stdlib.h>/* 二分查找法計(jì)算key出現(xiàn)的次數(shù) */ int CountTimesInArrays(int *arr,int len,int key) {if(arr==NULL || len<1)return 0;int start = 0;int end = len-1;int mid;while(start <= end){mid = (start+end)>>1;if(arr[mid] == key)break;else if(arr[mid] > key)end = mid-1;else start = mid+1;}//包括了出現(xiàn)0次的情況int times = 0;if(start <= end){int i;times = 1;for(i=mid+1;i<=end;i++)if(arr[i] == key)times++;for(i=mid-1;i>=start;i--)if(arr[i] == key)times++;}return times; } int main() {int n;while(scanf("%d",&n) != EOF){int *arr = (int *)malloc(n*sizeof(int));if(arr == NULL)exit(EXIT_FAILURE);int i;for(i=0;i<n;i++)scanf("%d",arr+i);int m;scanf("%d",&m);for(i=0;i<m;i++){int k;scanf("%d",&k);printf("%d\n",CountTimesInArrays(arr,n,k));}free(arr);arr = NULL;}return 0; }/**************************************************************????Problem: 1349????User: mmc_maodun????Language: C++????Result: Accepted????Time:800 ms????Memory:4928 kb****************************************************************/

轉(zhuǎn)載于:https://www.cnblogs.com/mfrbuaa/p/3923131.html

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】数字在排序数组中出现的次数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。