2022-01-27：供暖器。 冬季已经来临。 你的任务是设计一个
原创2022-01-27：供暖器。 冬季已经来临。 你的任务是设计一个
原创
2022-01-27：供暖器。
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
输入: houses = 1,2,3,4, heaters = 1,4
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
力扣475。
答案2022-01-27：
对房子和供暖器排序。
比如地点是7, 9, 14
供暖点的位置: 1 3 4 5 13 15 17
先看地点7
由1供暖，半径是6
由3供暖，半径是4
由4供暖，半径是3
由5供暖，半径是2
由13供暖，半径是6
由此可知，地点7应该由供暖点5来供暖，半径是2
再看地点9
供暖点不回退
由5供暖，半径是4
由13供暖，半径是4
由15供暖，半径是6
由此可知，地点9应该由供暖点13来供暖，半径是4
为什么是13而不是5？因为接下来的地点都会更靠右，所以半径一样的时候，就应该选更右的供暖点
再看地点14
供暖点不回退
由13供暖，半径是1
由15供暖，半径是1
由17供暖，半径是3
由此可知，地点14应该由供暖点15来供暖，半径是1
以此类推
时间复杂度：O(N)。
额外空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
houses := []int{1, 2, 3, 4}
heaters := []int{1, 4}
ret := findRadius(houses, heaters)
fmt.Println(ret)
}
func findRadius(houses []int, heaters []int) int {
sort.Ints(houses)
sort.Ints(heaters)
ans := 0
// 时间复杂度O(N)
// i是地点，j是供暖点
for i, j := 0, 0; i < len(houses); i++ {
for !best(houses, heaters, i, j) {
j++
}
ans = getMax(ans, abs(heaters[j]-houses[i]))
}
return ans
}
// 这个函数含义：
// 当前的地点houses[i]由heaters[j]来供暖是最优的吗？
// 当前的地点houses[i]由heaters[j]来供暖，产生的半径是a
// 当前的地点houses[i]由heaters[j + 1]来供暖，产生的半径是b
// 如果a < b, 说明是最优，供暖不应该跳下一个位置
// 如果a >= b, 说明不是最优，应该跳下一个位置
func best(houses, heaters []int, i, j int) bool {
return j == len(heaters)-1 || abs(heaters[j]-houses[i]) < abs(heaters[j+1]-houses[i])
}
func abs(a int) int {
if a < 0 {
return -a
} else {
return a
}
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。