新出炉的狗家电二面

int tmp=0;
vector<int> sum(nums.size(),0);
for(int i=0;i<nums.size();i++){
    sum[i]+=tmp+nums[i];
    tmp=sum[i];
}
return nums[upper_bound(sum.begin(),sum.end(),rand()%sum[sum.size()])-sum.begin()];

partial sum 然后二分找区间？

xihaokai1 发表于 2016-10-7 00:22
存partial sums， 可以做到logn

求问详细思路，存完prefix sum之后如何logN查找呢

1. public static int find(int[] array){
   
2.                 int[] sum=new int[array.length];
   
3.                 sum[0]=array[0];
   
4.                 for(int i=1;i<array.length;i++)sum[i]=array[i]+sum[i-1];
   
5.                 int start=0;
   
6.                 int end=sum.length-1;
   
7.                 int location=-1;
   
8.                 int target=(int)(Math.random()*(sum[array.length-1]-sum[0]+1))+sum[0];
   
9.                 while(start<end){
   
10.                         int mid=start+(end-start)/2;
    
11.                         if(sum[mid]==target){
    
12.                                 location=mid;
    
13.                                 break;
    
14.                         }else if(sum[mid]<target) {
    
15.                                 start=mid+1;
    
16.                         }else{
    
17.                                 end=mid;
    
18.                         }
    
19.                 }
    
20.                 if(location==-1)location=start;
    
21.                 if(location==0)return sum[0];
    
22.                 else return sum[location]-sum[location-1];
    
23.                
    
24.         }

复制代码

想问一下 楼主， google 电话面试的话， 需不需要 在网上跑 （RUN)你的代码？

看来google还是喜欢考tree，特别各种BST

这题要求和怎么也得O(N)吧？