Minimum Light Radius - 二分查找

• • • 题目地址
    • 题目描述
    • 思路
    • 代码(Python3)
    • 代码(Java)
    • 复杂度分析

题目地址

binarysearch.com/problems/Minimum-Light-Radius

题目描述

思路

1. 首先，思考了一下给的nums数组是不是有序的，事实证明是无序的，那先排个序
2. 因为半径可能有小数，比较麻烦，可以改成求最小直径，因为房子的坐标都是整数，那直径是房子坐标的差也一定是整数
3. 因为有三盏灯，直径的最大值是最右侧房子和最左侧房子坐标之差的1/3，因此右指针初始化为right = (nums[-1] - nums[0]) // 3
4. 如果当前直径mid可以覆盖所有的房子(allCovered == True)，当前mid可能偏大，也可能就是最小直径，令 right= mid - 1(如果确实偏大就丢弃了，如果确实是最小直径那循环会停止，left就是最小直径，返回left / 2)
5. 如果当前直径mid不可以覆盖所有房子(allCovered == False)，当前mid偏小，增大mid，left = mid + 1
6. 找到最小直径left后返回left的一半即为最小半径

• 判断是否可以覆盖所有房子的方法：

1. 三盏灯中的两盏肯定是放在两边的，就看中间那盏灯能不能覆盖剩下的房子，也就是看除去左右两盏灯覆盖的范围后的中间区域的房子的左右边界之差有没有比最小直径更小。
2. 通过二分法找中间区域房子的左边界leftBorder和右边界rightBorder
3. 如果右边界超出索引范围返回True（只有nums中地址不重复的房子数量<=3的时候会超出边界，这时候一定是返回True的）
4. 如果左右边界之差小于等于一盏灯可以覆盖的范围，返回True
5. 如果左右边界之差大于一盏灯可以覆盖的范围，返回False

代码(Python3)

class Solution:
    def solve(self, nums):
        nums.sort()
        left = 0
        right = (nums[-1] - nums[0]) // 3
        while left <= right:
            mid = (left + right) // 2
            if self.allCovered(mid, nums):
                right = mid - 1
            else:
                left = mid + 1
        return left / 2
    
    def allCovered(self, d, nums):
        # 1. 二分法找左边界
        target = nums[0] + d
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                # 是我们想要的，但我们更想要满足条件的最小mid
                right = mid - 1
            else:
                left = mid + 1
        leftBorder = left

        # 2. 二分法找右边界
        target = nums[-1] - d
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                # 是我们想要的，但我们更想要满足条件的最大mid
                left = mid + 1
            else:
                right = mid - 1
        rightBorder = right

        if rightBorder < 0 or nums[rightBorder] - nums[leftBorder] <= d:
            return True
        else:
            return False

代码(Java)

import java.util.*;

class Solution {
    public double solve(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = (nums[n - 1] - nums[0]) / 3;
        while(left <= right){
            int mid = (left + right) / 2;
            if(allCovered(mid, nums)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left / 2.0;
    }

    private boolean allCovered(int d, int[] nums){
        int target = nums[0] + d, n = nums.length;
        int left = 0, right = n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        int leftBorder = left;
        target = nums[n - 1] - d;
        left = 0;
        right = n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        int rightBorder = right;
        if(rightBorder < 0 || nums[rightBorder] - nums[leftBorder] <= d){
            return true;
        }else{
            return false;
        }
    }
}

复杂度分析

• 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)，排序最费时
• 空间复杂度： O ( 1 ) O(1) O(1)