Google 4/13 Phone Interview

給一個 array , decending order

ex: [5,

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

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

二次phone interview

求大神解法

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

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

If the array is [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], binary search take O(nlogn), so I think the linear pass is the best?

linear time 不行吗？
binary有人能给个思路？怎么觉得不行啊

像是[10,9,8,7,6,5,4,3,2,1]这种input，广是输出答案就要O(n), 所以O(logN)的算法应该是不行的

这个感觉是一个倍增(或者确切的说反向二分)的思想吧？ 每次往前面试探2*i(i从0开始 如果和当前数字相同就i+1， 不相同就i-1), 然后复杂度是类似o(N)?

只能想到O（N），看看高人有啥更好的方法