A C++ O((n+m)lg(m)) solution.


  • 0
    J
    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            
            int house_size = houses.size();
            if (house_size == 0) return 0;
            
            sort(heaters.begin(), heaters.end());
            
            int res = 0;
            for (auto& c : houses) {
                
                int idx = Bsearch(heaters, c);
            
                if (idx == 0) {
                    res = max(res, heaters[idx] - c);
                } else if (idx >= heaters.size()) {
                    res = max(res, c - heaters.back());
                } else {
                    res = max(res, min(heaters[idx] - c, c - heaters[idx - 1]));
                }
            }
            
            return res;
            
        }
        
        int Bsearch(vector<int>& nums, int val) {
            
            int l = 0, r = nums.size() - 1;
            while (l <= r) {
                int mid = l + ((r - l) >> 1);
                if (nums[mid] == val)
                    return mid;
                else if (nums[mid] < val)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            
            return l;
        }
    };
    

Log in to reply
 

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