BB挂面

上周五被鸽了面试，换了今天。

肯定挂了 一道easy题目的优化没写出来

一言不发烙印，很难受。估计是发现我那道题follow up判断的condition没想清楚，就做自己的事情去了，听的到对面有杂音

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

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

一个大概的思路。mid=(l+r)/2，移动mid到3个连续数字的第一位，然后判断左边右边数字的个数，哪边不能被3整除，就继续向哪遍搜索。

1. int findSingle(vector<int> nums){
   
2.     int l=0, r=nums.size()-1;
   
3.     while(l<=r){
   
4.         if(l==r) return l;
   
5.         if(r-l==4)
   
6.             return nums[l]==nums[l+1]?r-1:l+1;
   
7.         int mid=(l+r)/2;
   
8.         if(nums[mid]!=nums[mid+1] && nums[mid]!=nums[mid-1])
   
9.             return mid;
   
10.         else{
    
11.             int tmp=nums[mid];
    
12.             while(nums[mid]==tmp)
    
13.                 mid--;
    
14.         }
    
15.         int left_size=mid-l+1;
    
16.         if(left_size%3==0)
    
17.             l=mid+3;
    
18.         else
    
19.             r=mid;
    
20.     }
    
21.    
    
22.     return -1;
    
23. }

复制代码

补充内容 (2018-10-1 04:01):
边界条件写错了，怎么不能编辑自己的帖子啊。。

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

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

torymac1 发表于 2018-10-1 03:55
一个大概的思路。mid=(l+r)/2，移动mid到3个连续数字的第一位，然后判断左边右边数字的个数，哪边不能被3整 ...

对  面完和同学讨论了 就是这个思路， 判断该元素第一个位置的index是不是3的倍数，然后选择左边还是右边。边界单独判断

这题是easy?

用hash做不行吗？property 2 没太懂，什么样的数算similar？

yanmoviola 发表于 2018-10-1 01:35
用hash做不行吗？property 2 没太懂，什么样的数算similar？

那样是on了   烙印打的原题  不是similar 是identical   就是一样的数字总在一起的

clyyuanzi 发表于 2018-9-30 20:48
这题是easy?

不要求binary search的话真的只是easy

celine25 发表于 2018-10-1 02:37
不要求binary search的话真的只是easy

是不是可以用binary search 来判断上半区或者下半区的元素数目哪一个不是3的倍数？

celine25 发表于 2018-10-1 04:04
对  面完和同学讨论了 就是这个思路， 判断该元素第一个位置的index是不是3的倍数，然后选择左边还是右边 ...

感觉这题得算medium了 = =