Heaters – LeetCode 475

Problem

Description

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters’ warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.

Answer

Original

Code

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int n = heaters.size(), j = 0, res = 0;
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        for (int i = 0; i < houses.size(); ++i) {
            int cur = houses[i];
            while (j < n - 1 && abs(heaters[j + 1] - cur) <= abs(heaters[j] - cur)) {
                ++j;
            }
            res = max(res, abs(heaters[j] - cur));
        }
        return res;
    }
};

思路

优先进行两重排序，然后遍历houses，查找最近heaters的。记录下最大的距离就是答案了。时间复杂度$O(nlog{n})$，空间复杂度$O(1)$。
耗时$75$ ms，排名$26.54\%$

Better

思路

用lower_bound查找大于等于houses的heaters，用两个heaters夹着查找最近距离，然后的到距离的全局最大。时间复杂度$O(nlog{n})$，空间复杂度$O(1)$。
耗时$71$ ms，排名$10.29\%$

Code

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int res = 0;
        sort(heaters.begin(), heaters.end());
        for (int house : houses) {
            auto pos = lower_bound(heaters.begin(), heaters.end(), house);
            int dist1 = (pos == heaters.end()) ? INT_MAX : *pos - house;
            int dist2 = (pos == heaters.begin()) ? INT_MAX : house - *(--pos);
            res = max(res, min(dist1, dist2));
        }
        return res;
    }
};