go solution with binary search


  • 0
    H
    func lowerBound(arr []int, tar int) int {
        var lo int
        var hi = len(arr) - 1
    
        for lo <= hi {
            mid := (lo + hi) / 2
            if arr[mid] < tar {
                lo = mid + 1
            } else if arr[mid] == tar {
                return mid
            } else {
                hi = mid - 1
            }
        }
    
        return hi
    }
    
    func findRadius(houses []int, heaters []int) int {
        sort.IntSlice(houses).Sort()
        sort.IntSlice(heaters).Sort()
    
        var ret int
        for _, house := range houses {
            left := lowerBound(heaters, house)
            right := left + 1
    
            var min = 1 << 31
            if left >= 0 {
                d := house - heaters[left]
                if d < min {
                    min = d
                }
            }
    
            if right < len(heaters) {
                d := heaters[right] - house
                if d < min {
                    min = d
                }
            }
    
            if min > ret {
                ret = min
            }
    
        }
    
        return ret
    }
    

Log in to reply
 

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