C++ Solution Passed New Tests (500+ ms)


  • 0
    W

    One optimization: remove duplicates in heaters, and remove houses that locate on heaters. Ideas are similar with other solutions.

    int findRadius(vector<int>& houses, vector<int>& heaters) {
            unordered_set<int> heaterSet(heaters.begin(), heaters.end());
            vector<int> newHouses;
            for(auto h: houses) {
                if(!heaterSet.count(h)) 
                    newHouses.push_back(h);
            }
            vector<int> newHeaters(heaterSet.begin(), heaterSet.end());
            sort(newHouses.begin(), newHouses.end());
            sort(newHeaters.begin(), newHeaters.end());
            int minRadius = 0, index = 0;
            for(int i = 0; i < newHouses.size(); i++) {
                while(index +1 < newHeaters.size() && abs(newHeaters[index+1] - newHouses[i]) <= abs(newHeaters[index] - newHouses[i]))
                    index++;
                minRadius = max(minRadius, (int)abs(newHeaters[index] - newHouses[i]));
            }
            return minRadius;
        }
    

Log in to reply
 

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