Open azl397985856 opened 1 year ago
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
mini, maxi = 0, 10**9-1
houses, heaters = sorted(houses), sorted(heaters)
def isNotEnough(radius):
ranges = [[heater-radius, heater+radius] for heater in heaters]
for house in houses:
while ranges and house > ranges[0][1]:
ranges.pop(0)
if not ranges:
return True
if house < ranges[0][0]:
return True
return False
while mini < maxi:
middle = (maxi+mini)//2
if isNotEnough(middle):
mini = middle+1
else:
maxi = middle
return mini
class Solution {
// Sort + Binary Search
//Time Complexity : O((n + m)log(m)) 排序heater: mlogm, 遍历二分 nlogm ; Space Complexity: O(logn) sort need space
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int res = 0;
for (int house : houses) {
int left = binartSearch(heaters, house);
int right = left + 1;
int leftDistance = left >= 0 ? house - heaters[left] : Integer.MAX_VALUE;
int rightDistance = right >= heaters.length ? Integer.MAX_VALUE : heaters[right] - house;
res = Math.max(res, Math.min(leftDistance, rightDistance));
}
return res;
}
private int binartSearch(int[] nums, int target) {
if (nums[0] > target)
return -1;
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
// Sort + 2 Pointers
// Time Comlexity: O(mlogm + nlogn) sort need , we can ignore m+n(traverse need), Space Complexity: O(mlogm+nlogn) sort need
public int findRadius1(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int res = 0;
for (int i = 0, j = 0; i < houses.length; i++) {
int curDistance = Math.abs(houses[i] - heaters[j]);
while (j < heaters.length - 1 && curDistance >= Math.abs(houses[i] - heaters[j + 1])) {
j++;
curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
}
res = Math.max(res, curDistance);
}
return res;
}
}
Binary search
class Solution:
def solve(self, nums):
nums.sort()
def can_light_up(diameter):
index = bisect(nums, nums[0] + diameter * 3)
return True if index >= len(nums) else False
left = 0
right = nums[-1] - nums[0]
while left <= right:
mid = (left + right) >> 1
if can_light_up(mid):
right = mid - 1
else:
left = mid + 1
return left >> 1
Time: O(nlogn) Space: ?
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int l = 0; int r = max(houses[houses.size()-1], heaters[heaters.size()-1]) + 1;
auto judge = [&](int r) -> bool {
// 区域合并
// cout << r << " ";
int j = 0;
for(int i = 0; i < houses.size(); ++i) {
while(j < heaters.size() && heaters[j] + r < houses[i]) {
j++;
}
if(j == heaters.size()) return false;
if(abs(heaters[j] - houses[i]) <= r) continue;
return false;
}
return true;
};
while(l < r) {
int mid = (r - l) / 2 + l;
if(judge(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
/**
* @param {number[]} houses
* @param {number[]} heaters
* @return {number}
*/
var findRadius = function(houses, heaters) {
let res = 0;
//heaters 从大到小排序
heaters.sort((a, b) => a - b);
for (let house of houses) {
//找到距离大于该 house 最小的heater
const rightIndex = binarySearchRight(heaters, house);
//距离小于 house 的最大 heater
const leftIndex = rightIndex - 1;
const rightDis = rightIndex >= heaters.length ? Infinity : heaters[rightIndex] - house;
const leftDis = leftIndex < 0 ? Infinity : house - heaters[leftIndex];
//该 house 距离左右 heater 最近的距离
const curDis = Math.min(leftDis, rightDis);
//保证res 满足所有条件
res = Math.max(res, curDis);
}
return res;
};
//要找最大的符合条件的值
const binarySearchRight = (arr, target) => {
let start = 0;
let end = arr.length;
while (start <= end) {
const mid = Math.floor((start + end) / 2);
const val = arr[mid];
if (val <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
};
一次挪一个, 比较整体
if s == goal:
return True
s, goal = [*s], [*goal]
for x in range(len(s)):
a = s[0]
s.pop(0)
s.append(a)
if s == goal:
return True
return False
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
if s == goal:
return True
s, goal = [*s], [*goal]
for x in range(len(s)):
a = s[0]
s.pop(0)
s.append(a)
if s == goal:
return True
return False
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
复杂度分析
令 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 {
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;
ans = Math.max(ans, leftDistance < rightDistance ? leftDistance : rightDistance);
}
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 = left + (right - left + 1) / 2;
if (nums[mid] > target){
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
}
复杂度分析
class Solution: def solve(self, nums): nums.sort()
def can_light_up(diameter):
index = bisect(nums, nums[0] + diameter * 3)
return True if index >= len(nums) else False
left = 0
right = nums[-1] - nums[0]
while left <= right:
mid = (left + right) >> 1
if can_light_up(mid):
right = mid - 1
else:
left = mid + 1
return left >> 1
Minimum Light Radius
import bisect
def solve(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):
i = bisect.bisect_right(nums, end)
if i >= N:
return True
start = nums[i]
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, space: O(nlogn), O(1)
这次的题官网打不开,就做了官方题解里推荐的取暖器的题https://leetcode.cn/problems/heaters/
利用二分搜索最左边界,然后判断mid的值是否能覆盖所有房间
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
total = houses+heaters
total.sort()
def possible(r):
if bisect_left(houses, heaters[0]-r) == 0:
pass
else:
return False
for i in range(len(heaters)-1):
index_pre = bisect_right(houses, heaters[i]+r)
index_next = bisect_left(houses, heaters[i+1]-r)
if index_next > index_pre:
return False
if bisect_right(houses, heaters[-1]+r) < len(houses):
return False
else:
return True
l, r = 0, total[-1]-total[0]
while l <= r:
mid = (l+r)//2
if possible(mid):
r = mid-1
else:
l = mid+1
return l
T(n) = O(nlogn + lognlog(max_idx-min_idx)
S(n) = 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 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;
}
}
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。
说明:所有供暖器都遵循你的半径标准,加热的半径也一样。
示例 1:
输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。
示例 2:
输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。
示例 3:
输入:houses = [1,5], heaters = [2]
输出:3
from sortedcontainers import SortedList
class Solution:
def get_distance(self, house, heater_idx, heaters, n):
if heater_idx in [-1, n]:
return float("inf")
else:
return abs(house - heaters[heater_idx])
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
ans = 0
n = len(heaters)
# sorted array, O(NlogN)
heaters = SortedList(heaters)
for house in houses: # O(M)
# get the left and right heaters, O(logN)
right_heater_idx = heaters.bisect_left(house)
left_heater_idx = right_heater_idx-1
# get the min distance of left and right heaters, O(1)
distance = min(
self.get_distance(house, left_heater_idx, heaters, n),
self.get_distance(house, right_heater_idx, heaters, n)
)
ans = max(ans, distance)
return ans
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;
}
};
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
ans = 0
heaters.sort()
for house in houses:
j = bisect_right(heaters, house)
i = j - 1
rightDistance = heaters[j] - house if j < len(heaters) else float('inf')
leftDistance = house - heaters[i] if i >= 0 else float('inf')
curDistance = min(leftDistance, rightDistance)
ans = max(ans, curDistance)
return ans
"""
时间复杂度:o((m+n)logn)
空间复杂的:o(nlogn)
"""
可以先将heaters排序之后 循环house进行二分查找 查找到的i 如果小于0或者大于等于heater.length 设置maxvalue 否则取两者差值的最小者 最后的结果取每次递归的较大值
以下是另外一种双指针的方式
public int FindRadius(int[] houses, int[] heaters)
{
int ans = 0;
int d;
Array.Sort(houses);
Array.Sort(heaters);
int j = 0;
for (int i = 0; i < houses.Length; i++)
{
while (j < heaters.Length && heaters[j] < houses[i])
{
j++;
}
if (j == 0)
{
d = heaters[0] - houses[i];
}
else if (j == heaters.Length)
{
d = houses[i] - heaters[j - 1];
}
else
{
d = Math.Min(heaters[j] - houses[i], houses[i] - heaters[j - 1]);
}
ans = Math.Max(ans, d);
}
return ans;
}
复杂度分析
var findRadius = function(houses, heaters) {
houses.sort((a,b) => a-b)
heaters.sort((a,b) => a-b)
let res = 0
for(let i = 0, j = 0; i < houses.length; i++){
let curD = 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++
curD = Math.abs(houses[i] - heaters[j])
}
res = Math.max(res, curD)
}
return res
};
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;
}
};
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; ans = Math.max(ans, leftDistance < rightDistance ? leftDistance : rightDistance); } 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 = left + (right - left + 1) / 2;
if (nums[mid] > target){
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
}
class Solution:
def rotateString(self, A: str, B: str) -> bool:
n = len(A)
if A =="" and B =="":
return True
for i in range(n):
if B == A[i:] +A[0:i]:
return True
return False
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int a = 0, b = 0, ans = 0, n = houses.size(), m = heaters.size();
sort(begin(houses), end(houses));
sort(begin(heaters), end(heaters));
while(a < n){
while(b + 1 < m && (houses[a] << 1) >= heaters[b] + heaters[b+1]) ++b;
ans = max(ans, abs(houses[a++] - heaters[b]));
}
return ans;
}
};
写的力扣475的题目,二分思路。遍历每一个房屋,利用二分法找出每个房屋所处位置,找出左右最近加热器距离房屋距离。
var findRadius = function(houses, heaters) {
let ans = 0;
heaters.sort((a, b) => a - b);
for (const house of houses) {
const i = binarySearch(heaters, house);
const j = i + 1;
const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
const curDistance = Math.min(leftDistance, rightDistance);
ans = Math.max(ans, curDistance);
}
return ans;
};
const binarySearch = (nums, target) => {
let left = 0, right = nums.length - 1;
if (nums[left] > target) {
return -1;
}
while (left < right) {
const mid = Math.floor((right - left + 1) / 2) + left;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
# 复杂度分析
TC:O((n+m)logn),其中 m 是数组 houses的长度,n 是数组 heaters 的长度。 对数组 heaters 排序需要 O(nlogn)的时间。 使用二分查找对每个房屋寻找距离最近的供暖器,每次二分查找需要 O(logn)的时间,有 m房屋,因此需要 O(mlogn)的时间。 总时间复杂度是 O((n+m)logn)。
SC:O(logn),其中 n 是数组 heaters的长度。空间复杂度主要取决于排序所需要的空间。
TC: O(nlgn)
SC: O(n)
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int left = 0;
int right = Math.max(houses[houses.length - 1] - houses[0], heaters[heaters.length - 1]);
while (left < right) {
int mid = left + (right - left) / 2;
if (enough(houses, heaters, mid))
right = mid;
else
left = mid + 1;
}
return left;
}
private boolean enough(int[] houses, int[] heaters, int radius) {
for (int i = 0, j = 0; i < houses.length; i++) {
while (j < heaters.length && houses[i] > heaters[j] + radius) j++;
if (j == heaters.length
|| houses[i] < heaters[j] - radius
|| houses[i] > heaters[j] + radius)
return false;
}
return true;
}
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;
}
}
二分法
时间复杂度O((n+m)log n) 空间复杂度O(n)
ass 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;
}
}
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 {
// 找到房子左边最近的供暖器下标left
// 转化为:有序数组中找到最后一个小于等于target的元素 二分
// 则右边最近的供暖器就是left+1
int helper(vector<int>& heaters, int target){
// 处理边界
if(target > *(heaters.end()-1)){
return heaters.size()-1;
}
if(target < *(heaters.begin())){
return -1;
}
int left=0, right=heaters.size()-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(heaters[mid]>target){
right=mid-1;
}else{
left=mid;
}
}
return right;
}
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
// 排序
sort(heaters.begin(), heaters.end());
int ans=0;
for(auto& h: houses){
int left=helper(heaters, h);
int leftDistance=left==-1?INT_MAX:h-heaters[left]; // 根据是否在边界进行距离判断
int right=left+1;
int rightDistance=right==heaters.size()?INT_MAX:heaters[right]-h; // 根据是否在边界进行距离判断
ans=max(ans, min(leftDistance, rightDistance));
}
return ans;
}
};
var findRadius = function(houses, heaters) {
houses.sort((a, b) => a - b)
heaters.sort((a, b) => a - b)
let radius = 0
for (let i = 0; i < houses.length; i++) {
let left = 0, right = heaters.length - 1;
while (left < right - 1) {
const mid = (left + right) / 2 | 0
if (houses[i] > heaters[mid]) left = mid
else if (houses[i] < heaters[mid]) right = mid
else left = right = mid
}
const currentRadius = Math.min(Math.abs(houses[i] - heaters[left]), Math.abs(houses[i] - heaters[right]))
radius = Math.max(currentRadius, radius)
}
return radius
};
var findRadius = function(houses, heaters) {
let ans = 0;
heaters.sort((a, b) => a - b);
for (const house of houses) {
const i = binarySearch(heaters, house);
const j = i + 1;
const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
const curDistance = Math.min(leftDistance, rightDistance);
ans = Math.max(ans, curDistance);
}
return ans;
};
const binarySearch = (nums, target) => {
let left = 0, right = nums.length - 1;
if (nums[left] > target) {
return -1;
}
while (left < right) {
const mid = Math.floor((right - left + 1) / 2) + left;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
双指针
时间复杂度:O(nlogn) 排序 空间复杂度:O(1)
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
cur = 0
hindex = 0
hmax = len(heaters)-1
for h in houses:
while hindex < hmax and abs(h-heaters[hindex+1]) <= abs(h-heaters[hindex]):
hindex += 1
cur = max(cur,abs(h-heaters[hindex]))
return cur
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.