[CareerCup][Google Interview] 找出现次数

Given a sorted array and a number n.How can u find the number of occurance of n in the array . should be o(logn)

http://www.careercup.com/question?id=8877058

改变一下二分查找的方法，一次找到最左边，另一次找到最右边。

#include <iostream> #include <vector> using namespace std;int findPos(vector<int> &a, int left, int right, int key, bool findLeft) {if (left > right)return -1;int mid = (left + right) / 2;if (a[mid] == key){int pos = findLeft ? findPos(a, left, mid - 1, key, findLeft) : findPos(a, mid + 1, right, key, findLeft);return (pos == -1 ? mid : pos);}else if (a[mid] > key){return findPos(a, left, mid - 1, key, findLeft);}else{return findPos(a, mid + 1, right, key, findLeft);} }int main() {vector<int> a;for(int i = 0; i < 9; i++)for(int j = 0; j < 5; j++)a.push_back(i);int pos1 = findPos(a, 0, a.size() - 1, 5, true);int pos2 = findPos(a, 0, a.size() - 1, 5, false);cout << pos1 << ' ' << pos2 << endl; }

转载于:https://www.cnblogs.com/chkkch/archive/2012/10/29/2744640.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[CareerCup][Google Interview] 找出现次数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。