Java刷题随笔---475. 供热器
2021/12/20 17:19:47
本文主要是介绍Java刷题随笔---475. 供热器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
475. 供暖器 - 力扣(LeetCode) (leetcode-cn.com)
难度:中等
题目描述:冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。
说明:所有供暖器都遵循你的半径标准,加热的半径也一样。
分析
排序+双指针 此题使用双指针,为每一个房子位置寻找最近供热器位置,再将最大值找出,即为全局最小半径距离 使用双指针的前提就是两个数组是有序的, 所以需要对两个数组排序,此时时间复杂度:O(mlogm+nlogn)。 对于有序数组来说,只需要设置一个指针指向houses数组,一个指针指向heaters数组即可
解题
class Solution { public int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int m = houses.length; int n = heaters.length; int result = 0; for (int i = 0, j = 0; i < m; i++) { int curr = Math.abs(houses[i] - heaters[j]); while (j < n-1 && Math.abs(houses[i] - heaters[j+1]) <= curr){ j++; curr = Math.min(curr, Math.abs(houses[i] - heaters[j]) ); } result = Math.max(curr, result); } return result; } }
这篇关于Java刷题随笔---475. 供热器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21订单系统资料入门教程:轻松管理你的订单
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java订单系统资料:新手入门教程与实战指南
- 2024-09-21Java管理系统资料入门教程
- 2024-09-21从零开始学习Java监控系统资料
- 2024-09-21Java就业项目资料:新手入门的必备教程
- 2024-09-21Java全端资料:初学者指南
- 2024-09-21Java全栈资料入门教程及资源汇总
- 2024-09-21Java日志系统资料入门教程