Java教程

Java刷题随笔---475. 供热器

本文主要是介绍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. 供热器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!