My binary search and two pointers methods


  • 0
    class Solution {
    public:
    
        // two pointers
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            if (heaters.size() == 0 || houses.size() == 0) return 0;
            sort(houses.begin(), houses.end());
            sort(heaters.begin(), heaters.end());
            
            int p1 = 0, p2 = 0, res = 0;
            while (p1 < heaters.size() && heaters[p1] < houses[0]) p1++;
            p2 = p1;
            p1--;
            for (int house: houses) {
                while (p2 < heaters.size() && heaters[p2] < house) {
                    p1 = p2;
                    p2++;
                }
                
                int cur_res = 0;
                if (p1 < 0) cur_res = heaters[p2]-house;
                else if (p2 >= heaters.size()) cur_res = house - heaters[p1];
                else cur_res = min(heaters[p2]-house, house - heaters[p1]);
                res = max(res, cur_res);
            }
            return res;
        }
        
        // binary search
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            if (heaters.size() == 0 || houses.size() == 0) return 0;
            int res = 0;
            sort(heaters.begin(), heaters.end());
            for (int house: houses) {
                auto it = lower_bound(heaters.begin(), heaters.end(), house);
                
                int cur_res = 0;
                if (it == heaters.begin()) cur_res = *it - house;
                else {
                    auto pre = prev(it);
                    if (it == heaters.end()) cur_res = house - *pre;
                    else cur_res = min(house - *pre, *it - house);
                }
                res = max(res, cur_res);
            }
            return res;
        }
    };
    

Log in to reply
 

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