1.8 KiB
1.8 KiB
!
!
!
!
!
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;
}
}
!
!
!
!
!
!
!
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int ans = 0;
for (int i = 0, j = 0; i < houses.size(); i++) {
int curDistance = abs(houses[i] - heaters[j]);
while (j < heaters.size() - 1 && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])) {
j++;
curDistance = min(curDistance, abs(houses[i] - heaters[j]));
}
ans = max(ans, curDistance);
}
return ans;
}
};
!