首页 > 其他分享 >LeetCode题练习与总结:供暖器--475

LeetCode题练习与总结:供暖器--475

时间:2024-12-17 22:29:21浏览次数:10  
标签:heaters 供暖 -- 复杂度 距离 房屋 475 LeetCode left

一、题目描述

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

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

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

注意:所有供暖器 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^4
  • 1 <= houses[i], heaters[i] <= 10^9

二、解题思路

  1. 对供暖器的位置进行排序。
  2. 遍历每个房屋,找到距离该房屋最近的供暖器。这可以通过二分查找实现,因为供暖器的位置是有序的。
  3. 对于每个房屋,计算其与最近供暖器的距离,并更新最大距离。
  4. 最后,最大距离就是可以覆盖所有房屋的最小加热半径。

三、具体代码

import java.util.Arrays;

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        // 对供暖器位置进行排序
        Arrays.sort(heaters);
        int maxRadius = 0;

        // 遍历每个房屋
        for (int house : houses) {
            // 使用二分查找找到距离当前房屋最近的供暖器
            int left = 0, right = heaters.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (heaters[mid] < house) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 计算当前房屋与最近供暖器的距离
            int distance = Math.abs(heaters[left] - house);
            // 如果left不是第一个供暖器,计算当前房屋与左边供暖器的距离,取较小值
            if (left > 0) {
                distance = Math.min(distance, house - heaters[left - 1]);
            }
            // 更新最大距离
            maxRadius = Math.max(maxRadius, distance);
        }
        return maxRadius;
    }
}

在这段代码中,我们首先对供暖器的位置进行排序,然后遍历每个房屋,使用二分查找找到距离该房屋最近的供暖器,并计算距离。如果当前供暖器不是第一个供暖器,我们还需要计算房屋与左边供暖器的距离,并取较小值。最后,我们将计算出的距离与当前最大距离进行比较,并更新最大距离。最终返回的最大距离就是可以覆盖所有房屋的最小加热半径。

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 对供暖器位置进行排序的时间复杂度为 O(m log m),其中 m 是供暖器的数量。

  • 遍历每个房屋的时间复杂度为 O(n),其中 n 是房屋的数量。

  • 在每次遍历房屋时,我们使用二分查找来找到距离当前房屋最近的供暖器,二分查找的时间复杂度为 O(log m)。

将上述步骤合并,总的时间复杂度为 O(m log m + n log m)。由于 m 和 n 是输入规模,因此可以简化为 O((m + n) log m)。

2. 空间复杂度
  • 排序供暖器位置使用的空间复杂度为 O(1),因为排序是在原数组上进行的(假设使用的排序算法是原地排序)。

  • 代码中使用了几个基本类型的变量(left, right, mid, distance, maxRadius),它们使用的空间是常数级别的,因此空间复杂度为 O(1)。

综上所述,该算法的时间复杂度为 O((m + n) log m),空间复杂度为 O(1)。其中 m 是供暖器的数量,n 是房屋的数量。

五、总结知识点

  • 数组的排序

    • 使用 Arrays.sort() 方法对数组进行排序,这是一个常用的内置方法,它基于快速排序算法。
  • 二分查找算法

    • 通过二分查找找到数组中第一个大于或等于特定值的元素,这是算法中的一个高效查找方法。
  • 循环和条件判断

    • 使用 for 循环遍历房屋数组。
    • 使用 while 循环和条件判断来实现二分查找的逻辑。
  • 数学运算

    • 使用 Math.abs() 方法计算绝对值,即两个数之间的距离。
    • 使用 Math.min() 方法取两个数中的最小值。
    • 使用 Math.max() 方法更新最大值。
  • 数组索引操作

    • 通过索引访问数组元素,以及判断索引的有效性(例如,检查 left > 0 来确保不会越界)。
  • 基本数据类型

    • 使用 int 类型的变量来存储索引、距离和最大半径。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

标签:heaters,供暖,--,复杂度,距离,房屋,475,LeetCode,left
From: https://blog.csdn.net/weixin_62860386/article/details/144510998

相关文章

  • LeetCode题练习与总结:一和零--474
    一、题目描述给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。示例1:输入:strs=["10","0001",......
  • 【网络安全】Web安全基础- 第一节:web前置基础知识
    目录前言一、中间件1.1消息中间件1.2数据库中间件1.3web服务器中间件1.4应用服务器中间件1.5远程过程调用中间件二、源码**组成部分:**1、**前端(客户端)代码:**2、**后端(服务器端)代码**:3、资源文件:4、API接口:5、框架和库:6、配置文件:三、数据库四、CDN五、WAF六、DNS解析......
  • 在UE5 Cesium中点击地图生成Spline线
    本文中介绍在UE5Cesium中点击地图生成Spline线步骤包含了:1、鼠标点击时获得屏幕坐标2、将屏幕坐标转成世界坐标3、射线检测找到屏幕坐标在Cesium中的坐标4、生成Spline步骤1、2、3:https://blog.csdn.net/m0_48562356/article/details/144358371步骤4:新建一个Actor,......
  • C语言关于return在循环语句中的使用(求一个数是否为素数的过程中的思考)
    intjk(inta)//定义一个jk函数判断a是否是素数,是返回1,不是则返回0.{ inti;if(a<2){return0;} elseif(a==2) { return1; } else { for(i=2;i<=a-1;i++) { if(a%i==0) { return0; } } return1; } }intmain(......
  • 怎么提高自己的情商和口才?真正受欢迎的人,用这4个技巧提高
    高情商让你能够理解自己和他人的情绪,而良好的口才让你能清晰、自信地表达自己。如何提升情商和口才呢?本文提供实用的方法,让你逐步成长为沟通高手。一、提高情商的方法1.学会识别和管理自己的情绪提高情商的第一步是学会识别自己的情绪,并找到管理情绪的有效方式。情绪管理......
  • 常常被忽略,但是高情商表现的十大特征
    情商,这一概念我们并不陌生,它关乎着我们的情绪、情感,决定着我们处理人际关系的能力。有些人可能认为情商只是一种表面的技巧,但实际上,它却深深影响着我们的生活。情商高的人往往能够更好地处理生活中的各种困难,他们更懂得如何感知他人的情绪,理解他人的需求,从而建立起更为亲密、长......
  • 职场人如何提升职业技能?
    职场人如何提升职业技能?在职场中,每个人都像是一名航行在广阔大海上的水手,面对着不断变化的风浪和挑战。要想在这片职场海洋中稳步前行,甚至脱颖而出,提升职业技能是必不可少的。那么,职场人究竟该如何有效地提升自己的职业技能呢?以下是一些实用而具体的建议。一、持续学习与自我......
  • Hongcow Builds A Nation 题解
    HongcowBuildsANation题解洛谷。Codeforces。题目描述给定一张\(n\)个点,\(m\)条边的无向图,有\(k\)个点是特殊点。每个连通块中都得保证无重边、无自环,且最多只有一个特殊点。求最多还能加多少条边,满足以上条件。思路简述首先考虑以下有\(n\)个点的完全图共有多......
  • 搭建企业NextCloud并集成ONLYOFFICE
    部署安装1.1离线安装​ 使用能够安全拉取nextcloud镜像的服务器拉取镜像并打包成tar.gz通过sftp传输到准备好的部署服务器,这里使用的版本为aliyun镜像源拉去的latest版本如下[root@VM-12-10-centos~]#dockerimageinspectnextcloud:latest|grep-iversion"Dock......
  • 每日一道算法题之最小生成树之K算法
    最小生成树。有权无向图。把所有点连通起来的最小权重。k算法://Kruskal算法模版(洛谷)//静态空间实现//测试链接:https://www.luogu.com.cn/problem/P3366importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.io......