475. 供暖器

日期:2022-9-19 14:47 | 标签: | 阅读:16

这道题自己尝试了三种写法

  1. 暴力法,直接遍历 heaters 和 houses 数组,求得每个 house 距离 heater 的最小值,最后再遍历 houses 数组求最大值,时间复杂度来到了 n*m
  2. 优化暴力法中的直接遍历,对 heaters、houses 数组进行排序,查找时直接基于二分法,找到距离 house 的最小值,时间复杂度来到了 nlogm
  3. 基于微扰理论的解法, 时间复杂度来为 m+n,

leetcode 链接

function findRadius(houses: number[], heaters: number[]): number {
    houses = houses.sort((a,b) =>{
        return a- b;
    });
    heaters = heaters.sort((a,b) =>{
        return a- b;
    });

    let r = 0, hSize= heaters.length, curr = 0;
    heaters.unshift(Number.MIN_SAFE_INTEGER);
    heaters.push(Number.MAX_SAFE_INTEGER);

    for(let i = 0; i < houses.length; i++){

        while(curr < hSize + 2){
            if(heaters[curr] >= houses[i]){
                break;
            }
            curr++;
        }
        r = Math.max(r, Math.min( heaters[curr]- houses[i], houses[i] - heaters[curr-1]));
    }

    return r;
};

版权声明: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0
Copyright ©2013-2022 | 粤ICP备14081691号 | yipeng手工打造 | 联系方式