c++ solution


  • 0
    Z

    Do not need to sort houses, only need to sort the heaters (O(klogk)). For each house, find the closest heater with binary search. Time complexity: O(klogk) + O(n log k).
    ...
    class Solution {
    public:
    int findRadiusHelper(vector<int>& heaters, int curLoc) {
    // find closest heater location for curLoc
    int left = 0, right = heaters.size() - 1;
    while (left + 1 < right) {
    int mid = left + (right - left) / 2;
    if (heaters[mid] == curLoc) return 0;
    else if (heaters[mid] > curLoc) {
    right = mid;
    } else {
    left = mid;
    }
    }
    if (abs(heaters[left] - curLoc) > abs(heaters[right] - curLoc)) {
    return abs(heaters[right] - curLoc);
    } else {
    return abs(heaters[left] - curLoc);
    }
    }

    int findRadius(vector<int>& houses, vector<int>& heaters) {
        if (houses.empty()) return 0;
        sort(heaters.begin(), heaters.end());
        int res = 0;
        
        int curLoc;
        for (int i = 0; i < houses.size(); i++) {
            curLoc = houses[i];
            res = max(res, findRadiusHelper(heaters, curLoc));
        }
        return res;
    }
    

    };
    ...


Log in to reply
 

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