LeetCode 475. 供暖器

Categories:

题目描述
思路分析
1. 解法一：排序 + 二分（推荐）
相似题目

题目描述

✅ 475. 供暖器

思路分析

解法一：排序 + 二分（推荐）

核心思路：

将供暖器排序。

对每个房屋用二分找到最近供暖器位置。

取所有房屋最小距离中的最大值。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1)，排序可原地完成。

import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int res = 0;

        for (int house : houses) {
            int idx = Arrays.binarySearch(heaters, house);
            if (idx < 0) {
                idx = -idx - 1;
            }

            int dist1 = idx < heaters.length ? heaters[idx] - house : Integer.MAX_VALUE;
            int dist2 = idx > 0 ? house - heaters[idx - 1] : Integer.MAX_VALUE;

            res = Math.max(res, Math.min(dist1, dist2));
        }

        return res;
    }
}

import "sort"

func findRadius(houses []int, heaters []int) int {
	sort.Ints(heaters)
	res := 0

	for _, house := range houses {
		idx := sort.SearchInts(heaters, house)
		dist1 := 1 << 60
		dist2 := 1 << 60
		if idx < len(heaters) {
			dist1 = heaters[idx] - house
		}
		if idx > 0 {
			dist2 = house - heaters[idx-1]
		}

		if dist1 < dist2 {
			if dist1 > res {
				res = dist1
			}
		} else {
			if dist2 > res {
				res = dist2
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分
658. 找到 K 个最接近的元素	中等	二分
852. 山脉数组的峰顶索引	简单	二分
35. 搜索插入位置	简单	二分
1539. 第 k 个缺失的正整数	简单	二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/16728983