【Day 40 】2023-12-25 - 796. Minimum Light Radius

[azl397985856]

796. Minimum Light Radius

入选理由

暂无

题目地址

https://binarysearch.com/problems/Minimum-Light-Radius

前置知识

• 排序
• 二分法

  题目描述

  
  You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [3, 4, 5, 6] Output 0.5 Explanation If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.

[Danielyan86]

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        res = 0
        heaters.sort()  # 加热器排序
        for h in houses:  # 把房屋依次插入heaters list计算距离
            r = bisect.bisect_right(heaters, h)  # 找到最右边插入位置
            l = r - 1
            rightDistance = heaters[r] - h if r < len(heaters) else float("inf")  # 注意边界的处理
            leftDistance = h - heaters[l] if l >= 0 else float("inf")
            curDistance = min(leftDistance, rightDistance)
            res = max(res, curDistance)
        return res

[Chloe-C11]

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:

        '''
        1. 对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离；
        2. 对于所有的房屋，选择最大的上述距离。

        '''
        houses.sort()
        heaters.sort()

        # 用于检查在半径为 r 的情况下，是否可以将所有房屋加热
        # 遍历了每个房屋和供暖器的位置，并检查它们之间的距离是否小于或等于 r
        # 如果所有房屋都可以被加热，则返回 True；否则返回 False。
        def check(houses, heaters, r):
            index1, index2 = 0, 0
            while index1 < len(houses) and index2 < len(heaters):
                if houses[index1] >= heaters[index2] - r and houses[index1] <= heaters[index2] + r:
                    index1 += 1
                else:
                    index2 += 1
            return index1 >= len(houses)

        # 使用二分：检查是否可以使用半径为 mid 的供暖器加热所有房屋。如果是，则将 right 设置为 mid；否则将 left 设置为 mid。
        left, right = 0, max(houses[-1], heaters[-1])
        while left + 1 < right:
            mid = (left + right) // 2
            if check(houses, heaters, mid):
                right = mid
            else:
                left = mid
        if check(houses, heaters, left):
            return left
        else:
            return right

[ycan253]

class Solution: def findRadius(self, houses, heaters): med_list = [0] #把houses分成heaters个数的blocks，第一个block左端是0 houses = sorted(houses) heaters = sorted(heaters) res = 0 for i in range(len(heaters)-1): med_list.append((heaters[i]+heaters[i+1])/2)

取相邻heaters的平均值作为相邻block的左端右端（左开右合）

    med_list.append(max(houses)+1)#最后一个block右端是houses最大值+1
    i,j = 0,0 #两个列表分别一个指针
    while i < len(houses):
        while med_list[j] <= houses[i]:
            j+=1 #把每个房子i都放置在对应的block j
        j -= 1
        m = abs(houses[i]-heaters[j])
        res = max(res,m)
        i += 1   

[adfvcdxv]

var findRadius = function (houses, heaters) { houses.sort((a, b) => a - b); heaters.sort((a, b) => a - b); let ans = 0; for (let i = 0, j = 0; i < houses.length; i++) { let curDistance = Math.abs(houses[i] - heaters[j]); while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) { j++; curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j])); } ans = Math.max(ans, curDistance); } return ans; };

[larscheng]

思路

二分查找

• 每个房屋，与最近的供暖器距离为：最小加热半径 dis_houses = min(dis_left,dis_right)
• 所有房屋，所需的最小加热半径为：每个房屋最小加热半径的最大值

• 针对每个房屋，通过二分查找，找首个 >=house 的供暖器下标

  代码

  
  class Solution {
  public int findRadius(int[] houses, int[] heaters) {
      int ans = 0;
      Arrays.sort(heaters);
      for (int house : houses) {
          int i = binarySearch(heaters, house);
          int j = i + 1;
          int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
          int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
          int curDistance = Math.min(leftDistance, rightDistance);
          ans = Math.max(ans, curDistance);
      }
      return ans;
  }
  
  public int binarySearch(int[] nums, int target) {
      int left = 0, right = nums.length - 1;
      if (nums[left] > target) {
          return -1;
      }
      while (left < right) {
          int mid = (right - left + 1) / 2 + left;
          if (nums[mid] > target) {
              right = mid - 1;
          } else {
              left = mid;
          }
      }
      return left;
  }
  }

### 复杂度
- 时间复杂度：O((n + m) log n)
- 空间复杂度：O(log n)

[JinhMa]

class Solution {
    public double solve(int[] nums) {
        Arrays.sort(nums);
        int streetLength = nums[nums.length - 1] - nums[0];
        int low = 0, high = streetLength / 3 + 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (isPossible(nums, mid, 3)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (isPossible(nums, low, 3)) {
            return low / 2D;
        }
        return high / 2D;
    }

    private boolean isPossible(int[] nums, int diameter, int lightNumber) {
        int lightDiameter = -1;
        int currentLightNum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > lightDiameter) {
                currentLightNum++;
                lightDiameter = nums[i] + diameter;
            }
            if (currentLightNum > lightNumber) {
                return false;
            }
        }
        return true;
    }
}

[snmyj]

class Solution {
public:
    int findRadius(vector<int> &houses, vector<int> &heaters) {
        int ans = 0;
        sort(heaters.begin(), heaters.end());
        for (int house: houses) {
            int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            int i = j - 1;
            int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house;
            int leftDistance = i < 0 ? INT_MAX : house - heaters[i];
            int curDistance = min(leftDistance, rightDistance);
            ans = max(ans, curDistance);
        }
        return ans;
    }
};

[RealDuxy]

class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -> int:

    def isPossible(houses, heaters, r):
        hs_index, ht_index = 0, 0
        while hs_index < len(houses) and ht_index < len(heaters):
            if abs(houses[hs_index] - heaters[ht_index]) <= r:
                hs_index += 1
            else:
                ht_index += 1

        if hs_index < len(houses):
            return False
        elif hs_index == len(houses):
            return True

    if len(heaters) == 1:
        return max(abs(heaters[-1]-houses[0]), abs(heaters[0] - houses[-1]))

    # binary search

    left, right = 0, max(abs(heaters[-1]-houses[0]), abs(heaters[0] - houses[-1]))

    while left <= right:
        mid = (left+right) // 2

        if isPossible(houses, heaters, mid):
            right = mid - 1
        else:
            left = mid + 1

    return left

计算复杂度： 假设两个列表长度分别为M,N，最极端的情况N=1，二分查找的最大复杂度明显是 O(logM) 每次判断是否可以供暖的方法，使用双指针，所以还是O(M) So最大时间复杂度是O(MlogM)

空间复杂度 O（M+N）