生活随笔
收集整理的這篇文章主要介紹了
数字在数组中出现的次数
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
目：統計一個數字k在排序數組中出現的次數。例如輸入排序數組{1,2,3,3,3,3,4,5}和數字3，輸出4次
方案一：掃描數組，記錄第一個出現的k和最后一個k中間有多少個，時間復雜度為O(n)
方案二：由于數組是有序的，那么我們可以利用二分的思想，求出k在數組中的第一個位置和最后位置相減即可。時間復雜度為O(logN)
注意嚴格按照良好的C++編碼風格
[cpp]?view plaincopy
#include<cstdio>?? #include<cstring>?? #include<iostream>?? #include<algorithm>?? using?namespace?std;?? ?? ?? int?GetFirstIndex(int?*arrNum,?int?left,?int?right,?int?k){?? ????if(arrNum?==?NULL?||?left?>?right){?? ????????return?-1;?? ????}?? ????while(left?<=?right){?? ????????int?mid?=?(left+right)>>1;?? ????????if(arrNum[mid]?>?k){?? ????????????right?=?mid-1;?? ????????}?? ????????else?if(arrNum[mid]?<?k){?? ????????????left?=?mid+1;?? ????????}?? ????????else{?? ????????????if((mid?>?0)?&&?(arrNum[mid-1]?==?k)){?? ????????????????right?=?mid-1;?? ????????????}?? ????????????else{?? ????????????????return?mid;?? ????????????}?? ????????}?? ????}?? ????return?-1;?? }?? ?? ?? int?GetLastIndex(int?*arrNum,?int?left,?int?right,?int?k){?? ????if(arrNum?==?NULL?||?left?>?right){?? ????????return?-1;?? ????}?? ????while(left?<=?right){?? ????????int?mid?=?(left+right)>>1;?? ????????if(arrNum[mid]?>?k){?? ????????????right?=?mid-1;?? ????????}?? ????????else?if(arrNum[mid]?<?k){?? ????????????left?=?mid+1;?? ????????}?? ????????else{?? ????????????if((mid?<?right-1)?&&?(arrNum[mid+1]?==?k)){?? ????????????????left?=?mid+1;?? ????????????}?? ????????????else{?? ????????????????return?mid;?? ????????????}?? ????????}?? ????}?? ????return?-1;?? }?? ?? int?main(){?? ????int?arrNum[]?=?{1,2,3,3,3,3,4,5};?? ?????? ????int?firstIndex?=?GetFirstIndex(arrNum,?0,?7,?3);?? ????int?lastIndex?=?GetLastIndex(arrNum,?0,?7,?3);?? ????if(firstIndex?!=?-1?&&?lastIndex?!=?-1){?? ????????cout<<(lastIndex-firstIndex+1)<<endl;?? ????}?? ????else{?? ????????cout<<-1<<endl;?? ????}?? ????return?0;?? } ?
總結
以上是生活随笔為你收集整理的数字在数组中出现的次数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
