475. Heaters

题目

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters' warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

题目大意

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。

解题思路

给出一个房子坐标的数组，和一些供暖器坐标的数组，分别表示房子的坐标和供暖器的坐标。要求找到供暖器最小的半径能使得所有的房子都能享受到暖气。
这一题可以用暴力的解法，暴力解法依次遍历每个房子的坐标，再遍历每个供暖器，找到距离房子最近的供暖器坐标。在所有这些距离的长度里面找到最大值，这个距离的最大值就是供暖器半径的最小值。时间复杂度 O(n^2)。
这一题最优解是二分搜索。在查找距离房子最近的供暖器的时候，先将供暖器排序，然后用二分搜索的方法查找。其他的做法和暴力解法一致。时间复杂度 O(n log n)。

代码


package leetcode

import (
	"math"
	"sort"
)

func findRadius(houses []int, heaters []int) int {
	minRad := 0
	sort.Ints(heaters)
	for _, house := range houses {
		// 遍历房子的坐标，维护 heaters 的最小半径
		heater := findClosestHeater(house, heaters)
		rad := heater - house
		if rad < 0 {
			rad = -rad
		}
		if rad > minRad {
			minRad = rad
		}
	}
	return minRad

}

// 二分搜索
func findClosestHeater(pos int, heaters []int) int {
	low, high := 0, len(heaters)-1
	if pos < heaters[low] {
		return heaters[low]
	}
	if pos > heaters[high] {
		return heaters[high]
	}
	for low <= high {
		mid := low + (high-low)>>1
		if pos == heaters[mid] {
			return heaters[mid]
		} else if pos < heaters[mid] {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	// 判断距离两边的 heaters 哪个更近
	if pos-heaters[high] < heaters[low]-pos {
		return heaters[high]
	}
	return heaters[low]
}

// 解法二 暴力搜索
func findRadius1(houses []int, heaters []int) int {
	res := 0
	for i := 0; i < len(houses); i++ {
		dis := math.MaxInt64
		for j := 0; j < len(heaters); j++ {
			dis = min(dis, abs(houses[i]-heaters[j]))
		}
		res = max(res, dis)
	}
	return res
}