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

  1. nums = [3, 4, 5, 6]

Output

  1. 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.

思路

二分法

先排序，半径的长度为0~(最右-最左)，用这个直径作为mid，因为一共只有三栈灯，所以在确认两端的情况下，让中间的灯覆盖到剩余的中间区域

代码

  1. class Solution {
  2.     solve(nums: Array<number>): number {
  3.         const len:number = nums.length;
  4.         // 如果长度不满足，直接返回
  5.         if (len <= 3) return 0;
  6.         // 排序
  7.         nums = nums.sort((a, b) => a - b);
  8.         // 最左 和 最远的距离
  9.         let left:number = 0, right:number = nums[len - 1] - nums[0];
  11.         while(left < right) {
  12.             let mid:number = left + Math.floor((right - left) / 2);
  13.             // console.log(left, mid, right, this.isCover(nums, mid))
  14.             if (this.isCover(nums, mid)) {
  15.                 right = mid;
  16.             } else {
  17.                 left = mid + 1;
  18.             }
  19.         }
  20.         console.log(left)
  21.         return left / 2;
  22.     }
  24.     isCover(nums: Array<number>, dis: number) {
  25.         let cur:number = nums[0], len:number = nums.length;
  26.         let j:number = 0;
  27.         for(let i:number = 0; i < 3; i ++) {
  28.             cur += dis;
  29.             while(j < len && nums[j] <= cur) {
  30.                 j++;
  31.             }
  32.             if (j == len) break;
  33.             cur = nums[j]
  34.         }
  35.         return j == len;
  36.     }
  37. }

复杂度分析

时间复杂度 day32.[二分法].Minimum Light Radius - 图1#card=math&code=O%28%29)

空间复杂度 day32.[二分法].Minimum Light Radius - 图2#card=math&code=O%281%29)