供暖器

475. 供暖器

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

提示：

1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { } };

rust 解法, 执行用时: 8 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-25 14:45:54

impl Solution {
    // 双指针
    pub fn find_radius(mut houses: Vec<i32>, mut heaters: Vec<i32>) -> i32 {
        houses.sort_unstable();
        heaters.sort_unstable();
        let (mut ans, mut i, mut j, m, n) = (0, 0, 0, houses.len(), heaters.len());       
        while i < m {
            let mut pre = ans;
            ans = ans.max((houses[i] - heaters[j]).abs());
            while (j < n - 1 && (houses[i] - heaters[j]).abs() >= (houses[i] - heaters[j + 1]).abs()) {
                j += 1;
                ans = pre.max((houses[i] - heaters[j]).abs());
            }
            i += 1;
        }
        return ans;
    }
    // 二分搜索
    pub fn find_radius2(houses: Vec<i32>, heaters: Vec<i32>) -> i32 {
        let mut heaters = heaters;
        heaters.sort_unstable();
        let mut res = 0;
        for h in &houses {
            let i = heaters.binary_search(h);
            let tmp = match i {
                Ok(i) => 0,
                Err(i) => {
                    let mut dis = i32::MAX;
                    if i < heaters.len() && heaters[i] - *h < dis {
                        dis = heaters[i] - *h;
                    }
                    if i > 0 && *h - heaters[i - 1] < dis {
                        dis = *h - heaters[i - 1];
                    }
                    dis
                }
            };
            if tmp > res {
                res = tmp;
            }
        }

        res
    }
}

javascript 解法, 执行用时: 100 ms, 内存消耗: 44.6 MB, 提交时间: 2023-09-25 14:37:32

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    let ans = 0;
    heaters.sort((a, b) => a - b);
    for (const house of houses) {
        const i = binarySearch(heaters, house);
        const j = i + 1;
        const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
        const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
        const curDistance = Math.min(leftDistance, rightDistance);
        ans = Math.max(ans, curDistance);
    }
    return ans;
};

const binarySearch = (nums, target) => {
    let left = 0, right = nums.length - 1;
    if (nums[left] > target) {
        return -1;
    }
    while (left < right) {
        const mid = Math.floor((right - left + 1) / 2) + left;
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return left;
}

// 双指针
var findRadius2 = function(houses, heaters) {
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0, j = 0; i < houses.length; i++) {
        let curDistance = Math.abs(houses[i] - heaters[j]);
        while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
            j++;
            curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
        }
        ans = Math.max(ans, curDistance);
    }
    return ans;
};

cpp 解法, 执行用时: 68 ms, 内存消耗: 25.2 MB, 提交时间: 2023-09-25 14:36:32

class Solution {
public:
    // 排序 + 双指针
    int findRadius2(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int ans = 0;
        for (int i = 0, j = 0; i < houses.size(); i++) {
            int curDistance = abs(houses[i] - heaters[j]);
            while (j < heaters.size() - 1 && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])) {
                j++;
                curDistance = min(curDistance, abs(houses[i] - heaters[j]));
            }
            ans = max(ans, curDistance);
        }
        return ans;
    }
    
    // 排序 + 二分搜索
    int findRadius(vector<int> &houses, vector<int> &heaters) {
        int ans = 0;
        sort(heaters.begin(), heaters.end());
        for (int house: houses) {
            int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            int i = j - 1;
            int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house;
            int leftDistance = i < 0 ? INT_MAX : house - heaters[i];
            int curDistance = min(leftDistance, rightDistance);
            ans = max(ans, curDistance);
        }
        return ans;
    }
};

java 解法, 执行用时: 14 ms, 内存消耗: 45.6 MB, 提交时间: 2023-09-25 14:35:04

class Solution {
    // 排序 + 二分查找
    public int findRadius1(int[] houses, int[] heaters) {
        int ans = 0;
        Arrays.sort(heaters);
        for (int house : houses) {
            int i = binarySearch(heaters, house);
            int j = i + 1;
            int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
            int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
            int curDistance = Math.min(leftDistance, rightDistance);
            ans = Math.max(ans, curDistance);
        }
        return ans;
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (nums[left] > target) {
            return -1;
        }
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }

    // 排序 + 双指针
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0;
        for (int i = 0, j = 0; i < houses.length; i++) {
            int curDistance = Math.abs(houses[i] - heaters[j]);
            while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
                j++;
                curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
            }
            ans = Math.max(ans, curDistance);
        }
        return ans;
    }
}

golang 解法, 执行用时: 40 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-25 14:33:44

func findRadius(houses, heaters []int) (ans int) {
    sort.Ints(heaters)
    for _, house := range houses {
        j := sort.SearchInts(heaters, house+1)
        minDis := math.MaxInt32
        if j < len(heaters) {
            minDis = heaters[j] - house
        }
        i := j - 1
        if i >= 0 && house-heaters[i] < minDis {
            minDis = house - heaters[i]
        }
        if minDis > ans {
            ans = minDis
        }
    }
    return
}

golang 解法, 执行用时: 40 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-25 14:33:09

func findRadius(houses []int, heaters []int) int {
    ans := 0
    sort.Ints(houses)
    sort.Ints(heaters)
    j := 0
    for i, house := range houses {
        curDistance := abs(house - heaters[j])  // 房屋与加热器距离
        for j + 1 < len(heaters) && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1]) {
            j += 1
            curDistance = min(curDistance, abs(houses[i] - heaters[j]))  // 每个房屋与加热器最近距离
        }
        ans = max(ans, curDistance)
    }
    return ans
}

func abs(a int) int { if a < 0 { return -a }; return a }
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }

python3 解法, 执行用时: 108 ms, 内存消耗: 19 MB, 提交时间: 2023-09-25 14:29:25

class Solution:
    '''
    排序 + 双指针
    '''
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        ans = 0
        houses.sort()
        heaters.sort()
        j = 0
        for i, house in enumerate(houses):
            curDistance = abs(house - heaters[j])  # 房屋与加热器距离
            while j + 1 < len(heaters) and abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1]):
                j += 1
                curDistance = min(curDistance, abs(houses[i] - heaters[j]))  # 每个房屋与加热器最近距离
            ans = max(ans, curDistance)
        return ans

python3 解法, 执行用时: 112 ms, 内存消耗: 18.9 MB, 提交时间: 2023-09-25 14:27:26

class Solution:
    '''
    排序 + 二分搜索
    每个房屋，选择最近的供暖器，则加热半径就是所有最近距离的最大值
    '''
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        ans = 0
        heaters.sort()  # 加热器排序
        for house in houses:
            j = bisect_right(heaters, house)  # 每个房屋找到其距离最近的加热器
            i = j - 1
            rightDistance = heaters[j] - house if j < len(heaters) else float('inf')
            leftDistance = house - heaters[i] if i >= 0 else float('inf')
            curDistance = min(leftDistance, rightDistance)
            ans = max(ans, curDistance)
        return ans

上一题

下一题

详情