首页 > 其他 > 详细

LeetCode 475. Heaters

时间:2018-05-31 18:21:37      阅读:226      评论:0      收藏:0      [点我收藏+]

最大化最小值的问题。

方法一:直接做,顺便复习一下迭代器和lower_bound的用法。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        int maxdis=0;
        for (int i=0;i<houses.size();++i){
            if (houses[i]<=heaters[0]){
                maxdis=max(heaters[0]-houses[i],maxdis);
            }else if (houses[i]>=heaters[heaters.size()-1]){
                maxdis=max(houses[i]-heaters[heaters.size()-1],maxdis);
            }else{
                auto pos=lower_bound(heaters.begin(),heaters.end(),houses[i]);
                int tmp=min(houses[i]-*(--pos), *pos-houses[i]);
                maxdis = max(tmp,maxdis);
            }
        }
        return maxdis;
    }
};

 

方法二:分别计算每个house左面和右面距离最近的heater。时间复杂度比上述要低。学习一下 *max_element 和 *min_element 的用法。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int m=houses.size(), n=heaters.size(); 
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        vector<int> res(m,INT_MAX);
        
        for (int i=0,j=0;i<m&&j<n;){
            if (houses[i]<=heaters[j]){res[i] = heaters[j]-houses[i]; ++i;}
            else ++j;
        }
        
        for (int i=m-1,j=n-1;i>=0&&j>=0;){
            if (houses[i]>=heaters[j]){res[i] = min(houses[i]-heaters[j],res[i]); --i;}
            else --j;
        }
        return *max_element(res.begin(),res.end());
    }
};

 

LeetCode 475. Heaters

原文:https://www.cnblogs.com/hankunyan/p/9117838.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!