in JS. I just do not get it.


  • 0
    N

    Here is my code:

    /**
     * @param {number[]} houses
     * @param {number[]} heaters
     * @return {number}
     */
    var findRadius = function(houses, heaters) {
        function sortNumber(a, b) {return a-b;}
        heaters.sort(sortNumber);
        var radius = 0;
        for (i=0; i<houses.length; i++) {
            for (j=0; j<heaters.length-1; j++) {
                if (houses[i]*2 <= heaters[j] + heaters[j+1]) break;
            }
            radius = Math.max(radius, Math.abs(heaters[j]-houses[i]));
        }
        return radius;
    };
    

    It turned out to be TLE.
    However, the code below can pass and beat 90-100%.

    /**
     * @param {number[]} houses
     * @param {number[]} heaters
     * @return {number}
     */
    var findRadius = function(houses, heaters) {
        houses.sort(function(a,b){return a-b})
        heaters.sort(function(a,b){return a-b})
        var r=0
        var j=0
        for(var i=0;i<houses.length;i++){
            while(j<heaters.length-1 && ((heaters[j]+heaters[j+1])<=houses[i]*2)){
                j++
            }
            r=Math.max(r,Math.abs(heaters[j]-houses[i]))
        }
        return r
    };
    

    Can anyone tell me what the difference is here?

    In order to pass, I replaced to the code below, which is still far slower than the code above.

            var l=0, r=heaters.length-1;
            while (r-l>1) {
                var mid = Math.floor((r+l)/2);
                if (houses[i]>=heaters[mid]) l=mid;
                else r=mid;
            }
            
            radius = Math.max(radius, Math.min(Math.abs(heaters[r]-houses[i]), Math.abs(heaters[l]-houses[i])));
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.