非死不可店面

4/30号的店面，45mins，互相介绍5分钟，然后开始做题。一共一题然后有两问。不知道是不是力扣的原题。
给

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

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

rch + divide conquer

大家加油！

最后是怎么解的？我只想到两个for loop。类似刷题网私私儿。

写了个followup不知道对不对。。。

1. int DistinctCount(const vector<int>& A) {
   
2.     if (A.empty()) {
   
3.         return 0;
   
4.     }
   
5.     auto it = A.begin();
   
6.     int cnt = 1;
   
7.     while (true) {
   
8.         auto next_it = std::upper_bound(it, A.end(), *it);
   
9.         if (next_it == A.end()) {
   
10.             break;
    
11.         }
    
12.         it = next_it;
    
13.         ++cnt;
    
14.     }
    
15.     return cnt;
    
16. }

复制代码

lz 第一问直接two pointers是什么意思？是直接比较array[i]==array[i-1] 遇到不等的就把结果+1？

第一问：O(n) 遍历一遍，如果num[i] != num[i-1]则count++
第二问：如果用binarysearch找每个遇见的数字的upperbound这样最后不一定比O(n)快吧

dudatda 发表于 2020-5-26 12:45
第一问：O(n) 遍历一遍，如果num != num则count++
第二问：如果用binarysearch找每个遇见的数字的upperbou ...

对，但是前提是“里面重复的数字很多”。