Simple C++ solution (binary search)


  • 0
    J
    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            sort(heaters.begin(), heaters.end());
            int radius = INT_MIN;
            
            for(int a: houses){
                radius = max(radius, search_close(a, heaters));   
            }
            return radius;
        }
        
        int search_close(int p, vector<int> & heaters){
           int l = 0;
           int r = heaters.size()-1;
           while(l<r){
               int mid = l + (r-l)/2;
               if(heaters[mid] < p){
                   l = mid + 1;
               }else if(heaters[mid] > p){
                   r = mid;
               }else{
                   return 0;
               }
           }
           
           int to_return = abs(heaters[l] - p);
           if(l>0 &&  to_return > abs(heaters[l-1]-p)){
               to_return = abs(heaters[l-1]-p);
           }
           
           if(l<heaters.size()-1 &&  to_return > abs(heaters[l+1]-p))}
               to_return = abs(heaters[l+1]-p);
           }       
           return to_return;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.