two java solution using binary search and treeset


  • 0
    F
    • First, sort heaters.
    • Second, for each house, find the two nearest heaters, the one is on larger than house, another is no smaller than the house, then, get the minimum of the two, which means the smallest radius of the two nearest heaters.
    • Hold a variable to get the maximum value of the smallest radius for each house.
      Two corner cases need to be handled, one is the house position is smaller than the heaters[0], another is the house position is bigger than heaters[n-1].
      idx=~idx is used to get the insertion point of the searched item.
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(heaters);
            int n = heaters.length;
            int result = 0;
            for (int house : houses) {
                int idx = Arrays.binarySearch(heaters, house);
                if (idx < 0) {
                    idx = ~idx;
                    if (idx == 0) {
                        result = Math.max(result, heaters[0] - house);
                    } else if (idx == n) {
                        result = Math.max(result, house - heaters[n - 1]);
                    } else {
                        result = Math.max(result, Math.min(house - heaters[idx - 1], heaters[idx] - house));
                    }
                }
            }
            return result;
        }
    

    a less efficient way using treeset, the above solution takes 28ms, the following one takes 103ms:

        public int findRadius(int[] houses, int[] heaters) {
            TreeSet<Integer> treeSet = new TreeSet<>();
            for (int heater : heaters) {
                treeSet.add(heater);
            }
            int result = 0;
            for (int house : houses) {
                Integer floor = treeSet.floor(house);
                Integer ceiling = treeSet.ceiling(house);
                /*floor and ceiling cannot be null at the same time*/
                if (floor == null) {
                    result = Math.max(result, ceiling - house);
                } else if (ceiling == null) {
                    result = Math.max(result, house - floor);
                } else {
                    result = Math.max(result, Math.min(house - floor, ceiling - house));
                }
            }
            return result;
        }
    

Log in to reply
 

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