Open azl397985856 opened 2 years ago
思路: 唉,还是不会做。 本质是二分猜值,找出符合条件的最左值。 因此可以对所有可能性的半径进行猜值,满足则左移,代表最左二分。 关键是cover函数:先对nums[0]+d 二分找最右 记为leftBoard 在对nums[len(nums)-1] -d 二分找最左,记为RightBoard 随后判断, 如果 1.RightBoard<0 2. RightBoard - leftBoard <= d 则cover函数返回true
func solve(nums []int) int{
sort.Ints(nums)
n := len(nums)
if n <= 3 {
return 0
}
left := 0
right := (nums[n-1] - nums[0]) / 3
for left <= right {
mid := left + (right-left)/2
if canCoverAll(mid,nums){
right = mid - 1
}else{
left = mid + 1
}
}
return left / 2.0
}
func canCoverAll(d int,nums []int) bool{
target := nums[0]+d
n := len(nums)
left,right := 0,n
for left <= right{
mid := (left+right)/2
if nums[mid] > target{
right = mid - 1
}else{
left = mid + 1
}
}
leftBoard := left
target = nums[n-1]-d
for left <= right{
mid := left + (right-left)/2
if nums[mid] < target{
left = mid+1
}else{
right = mid-1
}
}
rightBoard := right
if (rightBoard<0||nums[rightBoard]-nums[leftBoard] <= d){
return true
}else{
return false
}
}
时间复杂度O(NlogN) 空间复杂度O(1)
func solve(nums []int) int{ sort.Ints(nums) n := len(nums) if n <= 3 { return 0 } left := 0 right := (nums[n-1] - nums[0]) / 3 for left <= right { mid := left + (right-left)/2 if canCoverAll(mid,nums){ right = mid - 1 }else{ left = mid + 1 } } return left / 2.0 }
func canCoverAll(d int,nums []int) bool{ target := nums[0]+d n := len(nums) left,right := 0,n for left <= right{ mid := (left+right)/2 if nums[mid] > target{ right = mid - 1 }else{ left = mid + 1 } } leftBoard := left target = nums[n-1]-d for left <= right{ mid := left + (right-left)/2 if nums[mid] < target{ left = mid+1 }else{ right = mid-1 } } rightBoard := right if (rightBoard<0||nums[rightBoard]-nums[leftBoard] <= d){ return true }else{ return false
参考题解, 排序 + possible二分
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
# 这里使用的是直径,因此最终返回需要除以 2
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
时间复杂度: O(nlogn+logn∗log(MAX−MIN))
空间复杂度: 取决于排序的空间消耗
C++ Code:
int upperBound(vector<int>& nums, int val, int left, int right)
{
while(left<=right)
{
int middle = left + (right - left)/2;
if(nums[middle]> val)
{
right = middle-1;
}
else // <=
{
left = middle+1;
}
}
// [right left]
return left;
}
bool isCover(vector<int>& nums, double val, int num)
{
int start = 0;
int end = nums.size()-1;
//cout << "val:" << val << "\n";
while(num)
{
int index = upperBound(nums, floor( nums[start] + 2.0* val +1e-9), start, end );
//cout << "index:" << index << "\n";
if(index>end)
return true;
start = index;
num--;
}
return false;
}
double solve(vector<int>& nums) {
sort(nums.begin(), nums.end());
double left = 0.;
double right = (nums.back() - nums.front())/2.0;
while(left<right-1e-9)
{
double middle = left + (right - left)/2.;
if(isCover( nums, middle, 3))
{
right = middle;
}
else
{
left = middle;
}
}
return left;
}
""" func solve(nums []int) int{ sort.Ints(nums) n := len(nums) if n <= 3 { return 0 } left := 0 right := (nums[n-1] - nums[0]) / 3 for left <= right { mid := left + (right-left)/2 if canCoverAll(mid,nums){ right = mid - 1 }else{ left = mid + 1 } } return left / 2.0 }
func canCoverAll(d int,nums []int) bool{ target := nums[0]+d n := len(nums) left,right := 0,n for left <= right{ mid := (left+right)/2 if nums[mid] > target{ right = mid - 1 }else{ left = mid + 1 } } leftBoard := left target = nums[n-1]-d for left <= right{ mid := left + (right-left)/2 if nums[mid] < target{ left = mid+1 }else{ right = mid-1 } } rightBoard := right if (rightBoard<0||nums[rightBoard]-nums[leftBoard] <= d){ return true }else{ return false } } """
It asks for the minimum possible radius. One way to solve it is that binary search among the possible radius space, define a function to test if the input radius is enough to cover all the houses, and find the minimum radius which is enough. The difficult part is how to define this helper function. It "bisect_right" each light's cover range one by one into the sorted array of houses to see which houses are covered by each light. The cover range always starts with the next to be covered house coordinate and ends with the coordinate+diameter.
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def enough(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
#bisect_right: the rightmost place in the sorted list to insert the given element
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = l + (r-l)//2
if enough(mid):
r = mid-1
else:
l = mid + 1
return l/2
TC: O(nlogn + logn*log(max(nums)-min(nums)) SC: O(n)
class Solution:
def solve(self, nums):
if len(nums) <= 3:
return 0
nums.sort()
left = 0
right = nums[-1] - nums[0]
while left <= right:
mid = left + (right - left) // 2
if self.can_cover(mid, nums, 3):
right = mid - 1
else:
left = mid + 1
return left / 2
def can_cover(self, target, nums, max_lights):
curr_range = nums[0] + target
lights = 1
for i in range(len(nums)):
if nums[i] > curr_range:
lights += 1
curr_range = nums[i] + target
if lights > max_lights:
return False
return True
Thoughts
Possible Binary Search, using template (low + 1 < hight)
Code
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
int streetLen = nums[nums.length - 1] - nums[0];
int low = 0, high = streetLen / 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 radius, int lightNumber) {
int lightRadius = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightRadius) {
currentLightNum++;
lightRadius = nums[i] + radius;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
Complexity Time: O(nlogn + logn(max + min)), nlogn for quick sort, logn for possible binary search, length of range is max - min Space: O(n)
class Solution: def solve(self, nums): nums.sort() N = len(nums) if N <= 3: return 0 LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
这里就拿力扣的取暖器来解答。 思路:首先对数据进行排序,排序完毕后,遍历房间,利用二分查找找到与房间位置加一最近的取暖器的位置,然后求出当前这个取暖器和房间的相对位置,与上一个取暖器与当前房间的相对位置相比较,取最小值。然后再将该数据与前面房间与取暖器的距离进行一个最大值处理。
func findRadius(houses []int, heaters []int) int {
sort.Ints(houses)
sort.Ints(heaters)
// var hon int = len(houses)
var hen int = len(heaters)
var res int = 0
for _, ho := range houses {
// 二分查找插入位置,结果始终是右侧的插入位置,所以结果范围是[0, len]
// 这里我们搜索当前房间位置+1,所以可以给当前房间供暖的只有 i 和 i - 1
// 再解释一下,我们查出来的i是 house+1 的插入位置,所以i对应的供暖器可能是 house+1 或者 大于house但离house最近 的位置
// i - 1对应的供暖器可能是 house 或者 小于house但离house最近 的位置
// 所以i和i- 1相当于覆盖了所有的可能性
r := sort.SearchInts(heaters, ho + 1)
l := r - 1
var r_dist int = math.MaxInt32;
var l_dist int = math.MaxInt32;
if r < hen {
r_dist = heaters[r] - ho
}
if 0 <= l {
l_dist = ho - heaters[l]
}
cur := min(l_dist, r_dist)
res = max(res, cur)
}
return res
}
func min(a int, b int) (int) {
if a < b {
return a
}
return b
}
func max(a int, b int) (int) {
if a > b {
return a
}
return b
}
时间复杂度:O((n+m)logn) 空间复杂度:O(logn)
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.
Minimum Light Radius | binarysearch
possible binary search
The diameter of light is from 0 to the biggest index of house in the beginning, we binary search the correct diameter,
if the value form left to mid is acceptable, then we move to [left, mid], else we move to [mid + 1, right]
acceptable means we can light up all the buildings with this Light diameter.
i.g. At least, the last lamp can light up the last building.
import java.util.*;
class Solution {
public double solve(int[] nums) {
final int NUM_OF_LIGHTS = 3;
int length = nums.length;
if (length <= NUM_OF_LIGHTS){
return 0;
}
Arrays.sort(nums);
int left = 0;
int right = nums[nums.length - 1];
while(left < right){
int mid = left + (right - left) / 2;
if(possible(nums,mid,NUM_OF_LIGHTS)){
right = mid;
}
else{
left = mid + 1;
}
}
return (left+0.0) / 2;
}
boolean possible(int[] nums, int diameter, int numsOfLights){
int start = nums[0];
int end = start + diameter;
int count = 0;
while(count < numsOfLights){
count++;
int idx = find(nums,end);
if (idx >= nums.length){
return true;
}
start = nums[idx];
end = start + diameter;
}
return false;
}
int find(int[] nums,int target){
int left = 0;
//it is possible that the target is more than nums.length - 1
//we make right = nums.length to deal with this situation.
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if(nums[mid]>target){
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
int streetLen = nums[nums.length - 1] - nums[0];
int low = 0, high = streetLen / 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 radius, int lightNumber) {
int lightRadius = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightRadius) {
currentLightNum++;
lightRadius = nums[i] + radius;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
Binary Search. Refer to official solution
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
Time: O(n log n + logn * log(MAX-MIN)) Space: O(1)
我是傻子, 题都看不明白
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
二分查找法
class Solution:
def solve(self, nums):
nums.sort()
# def possible(r):
# count, start = 0, -1
# for num in nums:
# if num <= start:
# continue
# else:
# start = num + r
# count += 1
# if count > 3:
# return False
# return True
def possible(r):
end = nums[0] + r
for i in range(3):
index = bisect.bisect_right(nums, end)
if index >= len(nums):
return True
end = nums[index] + r
return False
left, right = 0, max(nums)
while(left <= right):
mid = left + (right - left) // 2
if possible(mid):
right = mid - 1
else:
left = mid + 1
return left / 2
复杂度分析
class Solution:
def solve(self, nums):
nums.sort()
def check(ls,x):
num = 3
l = 0
for r in range(1,len(ls)):
while ls[r] - ls[l] > x:
l = r
num -= 1
if num == 0 and r < len(ls):
return False
return True
l , r = 0 , nums[-1]
while l < r:
mid = (l + r) >> 1
if check(nums,mid):
r = mid
else:
l = mid + 1
return l/2
class Solution: def solve(self, nums): nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def enough(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
#bisect_right: the rightmost place in the sorted list to insert the given element
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = l + (r-l)//2
if enough(mid):
r = mid-1
else:
l = mid + 1
return l/2
class Solution {
solve(nums) {
if(!nums) return;
nums.sort((a,b)=>a-b);
let min = 0;
let max = nums[nums.length-1] - nums[0];
let res = 0
while(min<=max){
const mid = min+Math.floor((max-min)/2.0);
if(isFind(nums,mid)){
res = mid;
max = mid - 1;
} else {
min = mid + 1;
}
}
function isFind(arr,mid){
let start = arr[0];
let end = start + mid;
let count = 1;
for(let i = 0; i < arr.length; i++){
if(arr[i] > end){
if(count == 3){
return false
} else {
start = arr[i];
end = start + mid;
count++;
}
}
}
return true;
}
return res / 2.0;
}
}
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 radius, int lightNumber) {
int lightRadius = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightRadius) {
currentLightNum++;
lightRadius = nums[i] + radius;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
用取暖器题目作为解答。
对房子和取暖器进行排序,然后从头开始遍历房子,去匹配第一个右边的取暖器,找到后根据位置进行半径计算,取左右最小的半径。
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(),houses.end());
sort(heaters.begin(),heaters.end());
int r=0;
int index=0;
for(int i=0;i<houses.size();i++){
while(index<heaters.size() && heaters[index]<houses[i]){
index++;
}
if(index==0){
r=max(r,heaters[index]-houses[i]);
}else if(index==heaters.size()){
return max(r,houses[houses.size()-1]-heaters[heaters.size()-1]);
}else{
r=max(r,min(heaters[index]-houses[i],houses[i]-heaters[index-1]));
}
}
return r;
}
};
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
# 这里使用的是直径,因此最终返回需要除以 2
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
这题可以使用二分的方式,需要自己写一个函数是否满足条件的判断。
import java.util.*; class Solution { public static double solve(int[] nums){ Arrays.sort(nums); double min = 0; double max = (nums[nums.length-1] - nums[0])/3; while (min<max){ double mid = (max-min)/2 + min; if(isPossible(nums,mid,3)){ max = mid; }else{ min = mid + 1; } } if (isPossible(nums, min, 3)) { return max / 2.0; } return max / 2.0; } private static boolean isPossible(int[] nums, double radius, int lightNumber) { double lightRadius = -1; int currentLightNum = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] > lightRadius) { currentLightNum++; lightRadius = nums[i] + radius; } if (currentLightNum > lightNumber) { return false; } } return true; } }
//抄答案 -- python -> js
const minLightRadius = (arr) => {
arr.sort((a, b) => a - b);
len = arr.length;
if (len <= 3) return 0;
let lights = 3;
const possible = (diameter) => {
let start = arr[0];
let end = start + diameter;
for (let i = 0; i < lights; i++) {
idx = bisect(arr, end);
if (idx > lights) return true;
start = arr[idx];
end = start + diameter;
}
return false;
};
let left = 0;
let right = arr[arr.length - 1] - arr[0];
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (possible(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left / 2;
};
function bisect(sortedList, el) {
if (!sortedList.length) return 0;
if (sortedList.length == 1) {
return el > sortedList[0] ? 1 : 0;
}
let lbound = 0;
let rbound = sortedList.length - 1;
return bisect(lbound, rbound);
function bisect(lb, rb) {
if (rb - lb == 1) {
if (sortedList[lb] < el && sortedList[rb] >= el) {
return lb + 1;
}
if (sortedList[lb] == el) {
return lb;
}
}
if (sortedList[lb] > el) {
return 0;
}
if (sortedList[rb] < el) {
return sortedList.length;
}
let midPoint = lb + Math.floor((rb - lb) / 2);
let midValue = sortedList[midPoint];
if (el <= midValue) {
rbound = midPoint;
} else if (el > midValue) {
lbound = midPoint;
}
return bisect(lbound, rbound);
}
}
难点是想到对照亮直径做二分,因为题目描述的是半径
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
// diameter min and max
int dMin = 0;
int dMax = nums[nums.length - 1] - nums[0];
int ans = 0;
while (dMin < dMax) {
int mid = (dMin + dMax) / 2;
if (isValidDiameter(nums, mid)) {
dMax = mid;
} else {
dMin = mid + 1;
}
}
return (double)dMax / 2;
}
private boolean isValidDiameter(int[] nums, int d) {
int start = nums[0];
int end = start + d;
int count = 1;
for (int num : nums) {
if (num > end) {
if (count == 3) {
return false;
} else {
start = num;
end = start + d;
count++;
}
}
}
return true;
}
}
TC: O(N * Log(max - min)) SC: O(1)
二分法
class Solution {
solve(nums) {
const canLight = (nums, d) => {
let start = nums[0];
let end = nums[nums.length - 1];
for (let i = 0; i < 3; i++) {
let border = start + d
if (border >= end) {
return true;
}
start = nums[nums.findIndex(num=>num>border)];
}
return false;
};
nums = [...(new Set(nums))].sort((v1, v2) => v1 - v2);
if (nums.length <= 3) return 0;
let low = 0;
let high = nums[nums.length - 1] - nums[0];
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
if (canLight(nums, mid)) {
high = mid-1;
} else {
low = mid + 1;
}
}
return low/2;
}
}
时间复杂度:O(nlogn)
空间复杂度:O(logn)
时间复杂度: O(nlogn + (logD * logD)) 排序是 nlogn,D 是最远的房子的距离,因为确认头尾两盏灯的覆盖也需要二分搜索,所以复杂度也是 logD。灯的半径是 log(D/6)。 空间复杂度: 排序的空间复杂度是 O(logn)
class Solution:
def solve(self, nums):
nums = sorted(nums)
sel = [nums[0]]
for n in nums:
if n == sel[-1]: continue
sel.append(n)
nums = sel
if len(nums) <= 3: return 0
left = 0
right = (nums[-1] - nums[0]) / 6.0 + 1
def check(r: float):
l = bisect.bisect_left(nums, nums[0] + r * 2)
if nums[l] <= nums[0] + r * 2:
l += 1
rr = bisect.bisect_right(nums, nums[-1] - r * 2)
if nums[rr] >= nums[-1] - r * 2:
rr -= 1
if rr <= l: return True
return (nums[rr] - nums[l]) / 2.0 <= r
while left < right:
mid = (left + right) / 2.0
if check(mid):
right = mid
else:
left = mid
if right - left < 1e-4:
break
return round(left,3)
二分
import java.util.*;
class Solution {
public double solve(int[] nums) {
int len = nums.length;
if (len <= 3) {
return 0;
}
Arrays.sort(nums);
int l = 0, r = nums[len - 1] - nums[0];
while (l <= r) {
int mid = (l + r) >>> 1;
if (isPossible(nums, mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return (l + 0.0) / 2;
}
private boolean isPossible(int[] nums, int mid) {
int light = 1, mostRight = nums[0] + mid;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] > mostRight) {
mostRight = nums[i] + mid;
++light;
}
}
return light <= 3;
}
}
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 radius, int lightNumber) {
int lightRadius = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightRadius) {
currentLightNum++;
lightRadius = nums[i] + radius;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
class Solution:
def solve(self, nums):
nums.sort()
n = len(nums)
if n <= 3:
return 0
def cover(nums,diameter):
start = nums[0]
end = start + diameter
for i in range(3):
idx = bisect_right(nums, end)
if idx >= n:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
ret = cover(nums, mid)
if ret:
r = mid - 1
else:
l = mid + 1
return l/2
time complexity: O(logN*logD + NlogN), N is the length of nums, D is the distance between the leftmost and rightmost house on the coordinate space complexity: O(1)
// 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.
# Understand:
[x - r, x + r], inclusive
3 street lights
Return the smallest r (double type)
# Plan:
if nums.length <= 3, return 0.0
sort nums first
left. right
2 * radius search space:
[0, right - left]
leftmost binary search
nums = [1, 1, 2, 3]
0, instead of 0.5
*/
// Time: O(nlogn)+O(log(max - min)) * O(logn)
import java.util.*;
class Solution {
public double solve(int[] nums) {
if (nums.length <= 3) return 0.0;
Arrays.sort(nums); // O(nlogn)
int min = nums[0], max = nums[nums.length - 1];
int left = 0, right = max - min; // 2*radius search space
// O(log(max - min)) * O(coverAllHouses)
while (left <= right) {
int mid = left + (right - left) / 2;
if (coverAllHouses(nums, mid)) {
right = mid - 1; // find one candidate radius, look more left to check
} else {
left = mid + 1;
}
}
return left / 2.0;
}
// nums is sorted,see if the current range covers all the houses (indexed based)
// O(logn) * 3 = O(logn)
private boolean coverAllHouses(int[] nums, int diameter) {
int start = nums[0];
int end = nums[0] + diameter;
// 3 lights
for (int light = 1; light <= 3; light++) {
int coverThroughIndexNum = coverThroughIndexNum(nums, end);
if (coverThroughIndexNum >= nums.length) {
return true;
}
// keep using the lights then if not
start = nums[coverThroughIndexNum]; // be careful of this line
end = start + diameter;
}
return false;
}
// binary search
// [1,2,3], 4
// return 3. --> if == nums.length, then true, cover all
// [1,4,5], 4
// return 2
// [1,4,4,5], 4
// return 3
// find the rightmost index to insert
// n = nums.length
// O(logn)
private int coverThroughIndexNum(int[] nums, double target) {
int left = 0, right = nums.length - 1; // indices
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// look more right
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// System.out.println(target + "," + left);
return left;
}
}
思路:
二分法
复杂度分析:
代码(C++):
实现一、
class Solution {
public:
double solve(vector<int>& nums) {
int n = nums.size();
int l = 0, r = nums[n - 1] - nums[0];
if (n <= 3) return 0;
sort(nums.begin(), nums.end());
while (l <= r) {
int mid = l + (r - l)/2;
if (allLitUp(nums, mid, n))
r = mid - 1;
else
l = mid + 1;
}
return (double)l/2;
}
private:
bool allLitUp(vector<int>& nums, int d, int n) {
int cur = nums[0];
int h = 0; // count of houses
for (int i = 0; i < 3; ++i) {
while (h < n && nums[h] <= cur + d)
h++;
if (h == n) break;
cur = nums[h];
}
return h == n;
}
};
思路 1.对nums进行排序 2.转换成二分查找问题
代码
class Solution:
def solve(self, nums):
nums.sort()
n = len(nums)
if n <= 3:
return 0
lights = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(lights):
idx = bisect_right(nums, end)
if idx >= n:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
复杂度分析
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
# 这里使用的是直径,因此最终返回需要除以 2
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
leetcode 475
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int res = 0;
for(int h : houses){
int leftHeater = bsr(h, heaters);
int rightHeater = leftHeater + 1;
int leftDis = leftHeater < 0 ? Integer.MAX_VALUE : h - heaters[leftHeater];
int rightDis = rightHeater >= heaters.length ? Integer.MAX_VALUE : heaters[rightHeater] - h;
int dis = Math.min(leftDis, rightDis);
res = Math.max(res, dis);
}
return res;
}
private int bsr(int target, int[] nums){
int l = 0, r = nums.length - 1;
if(nums[l] > target){
return -1;
}
while(l < r){
int mid = l + (r - l + 1)/2;
if(nums[mid] > target){
r = mid - 1;
}else{
l = mid;
}
}
return l;
}
}
func solve(nums []int) int{ sort.Ints(nums) n := len(nums) if n <= 3 { return 0 } left := 0 right := (nums[n-1] - nums[0]) / 3 for left <= right { mid := left + (right-left)/2 if canCoverAll(mid,nums){ right = mid - 1 }else{ left = mid + 1 } } return left / 2.0 }
func canCoverAll(d int,nums []int) bool{ target := nums[0]+d n := len(nums) left,right := 0,n for left <= right{ mid := (left+right)/2 if nums[mid] > target{ right = mid - 1 }else{ left = mid + 1 } } leftBoard := left target = nums[n-1]-d for left <= right{ mid := left + (right-left)/2 if nums[mid] < target{ left = mid+1 }else{ right = mid-1 } } rightBoard := right if (rightBoard<0||nums[rightBoard]-nums[leftBoard] <= d){ return true }else{ return false } }
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
这个题要先想到:在给定半径的情况下,验证三个灯是否能cover所有点。这个点没想到就很难展开思路。验证三个灯是否能覆盖所有点显然可以使用二分法。同样,确定半径也可以使用二分法。
r
的情况下,三个灯是否能覆盖所有点,第一个灯light
一定在nums[0]+r
的位置,第二个灯则在light+r
的位置,但这是具体值,需要在nums中找到light+r
元素(二分要素察觉),以此类推摆满3个灯并返回bool值。需要进行三次二分查找,复杂度为$O(\log n)$r
的取值范围为$[0,(nums[-1]-nums[0])/2]$,而nums
中的元素均为整数,所以半径的步进大小为0.5,枚举r
判断是否能cover所有点即可。枚举可以直接循环,但二分显然更加快,复杂度为$O(\log{(max(nums)-min(nums))})$。class Solution:
# 这个题要先想到:*在给定半径的情况下,验证三个灯是否能cover所有点*。这个点没想到就很难展开思路。
# 验证三个灯是否能覆盖所有点显然可以使用二分法。同样,确定半径也可以使用二分法。
# - 排序+能力检测二分:复杂度$O((n+\log{[max(nums)-min(nums)]})*\log n)$
# - 先排序,复杂度$O(n\log n)$
# - 能力检测二分:用二分法确定在给定半径`r`的情况下,三个灯是否能覆盖所有点,第一个灯`light`一定在
# `nums[0]+r`的位置,第二个灯则在`light+r`的位置,但这是具体值,需要在nums中找到`light+r`元素(二分
# 要素察觉),以此类推摆满3个灯并返回bool值。需要进行三次二分查找,复杂度为$O(\log n)$
# - 半径`r`的取值范围为$[0,(nums[-1]-nums[0])/2]$,而`nums`中的元素均为整数,所以半径的步进大小
# 为0.5,枚举`r`判断是否能cover所有点即可。枚举可以直接循环,但二分显然更加快,复杂度为
# $O(\log{(max(nums)-min(nums))})$。
def solve(self, nums):
nums.sort()
n = len(nums)
if n <= 3:
return 0
def possible(r):
idx = 0
for i in range(3):
light = nums[idx] + r
idx = bisect.bisect_right(nums, light + r)
if idx >= n:
return True
return light + r >= nums[-1]
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
if possible(mid / 2):
right = mid
else:
left = mid + 1
return left / 2
二分法
2 * r
的边界为[0, max(nums) - min(nums)]
,最小直径可用二分法在其中查找r
第一盏灯一定覆盖了最左的房屋即x1 - r <= nums[0]
然后二分查找三盏灯是否可以覆盖全部房屋,可以则最小直径在[0, 2 * r]
之间,否则在[2 * r, max(nums) - min(nums)]
之间
class Solution:
def solve(self, nums):
n = len(nums)
if n <= 3:
return 0
nums.sort()
def check(dis):
start = nums[0]
end = start + dis
for _ in range(3):
ind = bisect_right(nums, end)
if ind >= n:
return True
start = nums[ind]
end = start + dis
return False
l, r = 0 ,nums[-1] - nums[0]
while l < r :
mid = (l + r) // 2
if check(mid):
r = mid
else:
l = mid + 1
return l / 2.0
Minimum Light Radius
思路
对nums进行从小到大的排序,直径的值空间为[0, nums[-1] - nums[0]] ,对该范围进行二分搜索。
代码
class Solution {
solve(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
if(n <= 3) return 0;
let left = 0, right = nums[n - 1] - nums[0];
while(left < right){
let mid = (left + right) >>> 1;
if(this.check(nums, mid)){
right = mid;
}else{
left = mid + 1;
}
};
return left / 2;
}
check(arr, diameter){
let start = arr[0], end = start + diameter;
let cnt = 0;
for(let i = 0; i < 3; i++){
let index = this.find_right(arr, end);
if(index === arr.length) return true;
start = arr[index];
end = start + diameter;
};
return false;
}
find_right(arr, value){
const n = arr.length;
let left = 0, right = n;
while(left < right){
let mid = (left + right) >>> 1;
if(arr[mid] <= value) left = mid + 1;
else right = mid;
};
return left;
}
}
复杂度分析
class Solution { solve(nums) { nums.sort((a, b) => a - b); const n = nums.length; if(n <= 3) return 0;
let left = 0, right = nums[n - 1] - nums[0];
while(left < right){
let mid = (left + right) >>> 1;
if(this.check(nums, mid)){
right = mid;
}else{
left = mid + 1;
}
};
return left / 2;
}
check(arr, diameter){
let start = arr[0], end = start + diameter;
let cnt = 0;
for(let i = 0; i < 3; i++){
let index = this.find_right(arr, end);
if(index === arr.length) return true;
start = arr[index];
end = start + diameter;
};
return false;
}
find_right(arr, value){
const n = arr.length;
let left = 0, right = n;
while(left < right){
let mid = (left + right) >>> 1;
if(arr[mid] <= value) left = mid + 1;
else right = mid;
};
return left;
}
}
class Solution:
def solve(self, nums):
nums.sort()
LIGHTS = 3
if len(nums) <= LIGHTS:
return 0
def possible(diameter):
start = nums[0]
end = nums[0] + diameter
for i in range(LIGHTS):
idx = bisect.bisect_right(nums, end)
if idx >= len(nums):
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l/2
class Solution:
def solve(self, nums):
nums.sort()
light = 3
N = len(nums)
if N <= 3:
return 0
def possible(diameter):
start = nums[0]
end = nums[0] + diameter
for i in range(light):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = nums[idx] + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l/2
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
# 这里使用的是直径,因此最终返回需要除以 2
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
能力检测二分:这种二分最核心的店在于模拟题目要求,也就是possible里的模拟过程是核心代码
这道题进入possible的直径D在二分上需要选择为int(向下取整),我是这么理解的:因为所有的房子之间的距离都是整数,所以半径要么是x要么是x.5,当然直径就一定是整数,所以二分区间调整的时候可以采用+1或-1;如果存在坐标为小数(当然必须要有最小标准间距,否则线性了还怎么二分)的房屋,那么就不能用+1或-1来调整二分区间了
反正这个距离的取整就是有一点需要理解
int find(vector<int>& nums,int target){
int l = 0;
int r = nums.size()-1;
while (l <= r) {
int mid = (r - l) / 2 + l;
if (nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return r + 1;
}
bool possible(vector<int>& nums,int D,int size){
double end = nums[0]+D;
for(int i = 0;i<3;i++){
int cur = find(nums,end);
if(cur>=size) return true;
end = nums[cur]+D;
}
return false;
}
double solve(vector<int>& nums) {
int size = nums.size();
if(size<=3) return 0;
sort(nums.begin(),nums.end());
double l = 0;
double r = nums[size-1]-nums[0];
while(l<=r){
int mid = (r-l)/2+l;
if(possible(nums,mid,size)) r = mid-1;
else l = mid+1;
}
return l/2;
}
复杂度分析
时间复杂度:O(nlogn) 排序
空间复杂度:O(1) 排序
无 看答案
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 radius, int lightNumber) {
int lightRadius = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightRadius) {
currentLightNum++;
lightRadius = nums[i] + radius;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
时间 O(NlogN) 空间O(N)
二分法。看了题解做的。
//https://binarysearch.com/problems/Minimum-Light-Radius
import java.util.*;
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
double r = 0;
double l = (nums[nums.length-1] - nums[0]) / 3;
while (r < l){
double m = (l-r) / 2 + r;
if (check(nums, m, 3)){
l = m;
}else {
r = m + 1;
}
}
if (check(nums, r, 3)){
return l / 2.0;
}
return l / 2.0;
}
private boolean check(int nums[], double ra, double liNum){
double lightRa = -1;
int curLiNum = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] > lightRa){
curLiNum++;
lightRa = nums[i] + ra;
}
if (curLiNum > liNum){
return false;
}
}
return true;
}
}
复杂度分析
思路 二分
代码
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
复杂度 时间 O(nlogn) 空间 O(1)
遇到困难直接投降
import java.util.*;
class Solution {
private static final double EPS = 1E-6d;
public double solve(int[] nums) {
Arrays.sort(nums);
double l = EPS, r = nums[nums.length - 1] - nums[0];
while (r - l >= EPS) {
double m = (l + r) / 2d;
if (can(nums, m))
r = m - EPS;
else
l = m + EPS;
}
return l;
}
private boolean can(int[] nums, double m) {
int quota = 3;
final double range = m * 2d;
for (int i = 0, j = -1; i != nums.length; i++) {
j = i;
while (j + 1 != nums.length && nums[j + 1] - nums[i] <= range) j++;
if (quota-- == 0)
return false;
i = j;
}
return true;
}
}
二分法
import java.util.*;
class Solution {
public double solve(int[] nums) {
if (nums == null || nums.length == 0) {
return 0D;
}
int length = nums.length;
Arrays.sort(nums);
int radiusMax = nums[length - 1] - nums[0];
int left = 0, right = radiusMax / 3 + 1;
while (left + 1 < right) {
int mid = left + ((right - left) >> 1);
if (isValid(nums, mid, 3)) {
right = mid;
} else {
left = mid;
}
}
if (isValid(nums, left, 3)) return left / 2D;
return right / 2D;
}
// nums 房子排序后的数组,radius 灯照射的半径,num 灯的数量
private boolean isValid(int[] nums, int radius, int num) {
int radiusCoverd = -1; // 覆盖的半径
int numUsed = 0; // 已经使用的灯的数量
for (int i = 0; i < nums.length; i++) {
// 如果当前的房子不能被路灯照射到
if (nums[i] > radiusCoverd) {
// 新加一个路灯,新加路灯的照射覆盖区域(往右)是 nums[i] + radius
radiusCoverd = nums[i] + radius;
// 路灯数量+1
numUsed++;
}
// 如果已经使用的路灯数量超过了规定的数量(本题是3个),返回 false
if (numUsed > num) {
return false;
}
}
// 如果所有房子均能被照射到且路灯数量不超过3个,则返回 true
return true;
}
}
796. Minimum Light Radius
入选理由
暂无
题目地址
https://binarysearch.com/problems/Minimum-Light-Radius
前置知识
题目描述
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.