心塞的fb电面跪经

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

worst case klgn?

Q2:

1. vector<pair<int, int>> getCount(vector<int>& a) {
   
2.     vector<pair<int, int>> res;
   
3.     for (auto i = a.begin(), j = upper_bound(i,a.end(),*i); i < a.end(); i = j)
   
4.         res.emplace_back(*i, j-i);
   
5.     return res;
   
6. }

复制代码

zzgzzm 发表于 2017-8-10 18:44
Q2:

印象中upper_bound是 O(n)吧

LeoJY 发表于 2017-8-18 09:54
印象中upper_bound是 O(n)吧

对于sorted random iterator-able container, upper_bound and lower_bound都是O(logN).