Google 4/13 Phone Interview

樓主貌似是太准求最優解法了。這題好像就是 leet80 的變種

1. vector<int> findChanges(vector<int> & nums){
   
2.     vector<int> res;
   
3.     helper(nums, 0, nums.size()-1, res);
   
4.     return res;
   
5. }
   
6. void helper(vector<int> &nums, int l, int r, vector<int> & res){
   
7.     if(l+1==r){
   
8.         if(nums[l]!=nums[r])
   
9.             res.push_back(r);
   
10.         return;
    
11.     }
    
12.     int mid = (l+r)/2;
    
13.     if(nums[l]!=nums[mid])
    
14.         helper(nums, l, mid, res);
    
15.     if(nums[mid]!=nums[r])
    
16.         helper(nums, mid, r, res);
    
17. }

复制代码

l+1==r时，判断l和r处是否相等，不等说明r处发生了改变；
l+1<r时，取mid = (l+r)/2，如果l和mid不相等，递归左边；mid和r不相等，递归右边
并不是严格O(logN)的，最坏情况是O(N)

您好！
本帖隐藏的内容需要积分高于 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

面试官要求用binary search吗？不接受O(n)的解法吗？

cocoon8892 发表于 2018-4-17 11:17
面试官要求用binary search吗？不接受O(n)的解法吗？

是的
我先說了O(N) 他希望更好

借用binary是为了省去check重复区间的时间把？ if(l < r && nums[l] == nums[r]) return; //skip

我只能想到直接从头到尾遍历，然后每次和下一个不相等就输出一下……

但是楼主的方法确实比较好，最乱的情况时间复杂度一样，但是比如100个10，100个9这种特殊情况才会快一点吧