475. Heaters

一開始我只能想到O(n²)的解, 就是看每個熱水器跟家的距離, 再找出所有距離的最大值, 當作半徑, 但會TLE

class Solution
{
public:
    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        vector<int> houses_to_heater_distance(houses.size(), INT_MAX);
        for (int i = 0; i < houses.size(); i++)
        {
            for (int j = 0; j < heaters.size(); j++)
            {
                houses_to_heater_distance[i] = min(abs(heaters[j] - houses[i]), houses_to_heater_distance[i]);
            }
        }
        int res = 0;
        for (auto &n : houses_to_heater_distance)
        {
            res = max(res, n);
        }
        return res;
    }
};

簡單來說, 你得去找離房子最近的兩邊熱水器, 然後去算跟兩邊的距離是多少, ，注意 binary search可能會超界, 要小心(代表根本沒那個熱水器)

class Solution
{
public:
    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        int n = heaters.size();
        int res = 0;
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        for (auto house : houses)
        {
            int l = 0;
            int r = n - 1;
while (l <= r)
            {
                int mid = (l + r) / 2;
                if (heaters[mid] == house)
                {
                    l = mid;
                    r = mid;
                    break;
                }
                if (heaters[mid] < house)
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
            int dist1 = r < 0 ? INT_MAX : abs(house - heaters[r]);
            int dist2 = l == n ? INT_MAX : abs(heaters[l] - house);
            res = max(min(dist1, dist2), res);
        }
return res;
    }
};