LeetCode演算法題-Heaters（Java實現）
這是悅樂書的第239 次更新，第252 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第106題（順位題號是475）。冬天來了！您在比賽期間的第一份工作是設計一個固定溫暖半徑的標準加熱器，以加熱所有房屋。現在，您可以在水平線上獲得房屋和加熱器的位置，找出加熱器的最小半徑，以便所有房屋都能被這些加熱器覆蓋。因此，您的輸入將分別是房屋和加熱器的位置，您的預期輸出將是加熱器的最小半徑。例如：
輸入：[1,2,3]，[2]
輸出：1
說明：唯一的加熱器在位置2，如果我們使用半徑1標準，那麼所有房屋都可以加熱。
輸入：[1,2,3,4]，[1,4]
輸出：1
說明：兩個加熱器在位置1和4，我們需要使用半徑1標準，然後所有房屋都可以加熱。
注意：
-
您給出的房屋和加熱器的數量是非負數，不會超過25000。
-
您給出的房屋和加熱器的位置是非負的，不會超過10 ^ 9。
-
只要房子在加熱器的溫暖半徑範圍內，就可以加熱。
-
所有加熱器都遵循半徑標準，溫暖半徑也是如此。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
我們將房子、加熱器都先排序，然後利用兩層迴圈，外層遍歷房子，內層遍歷加熱器，每次獲取到房子，就去比較對應位置的左右加熱器，拿他們的位置值與當前房子的位置值之間的絕對值做比較，如果右邊的加熱器的位置值絕對值小於左邊的，就繼續向右比較，也就是取當前房子在左右加熱器之間的最小半徑。然後將當前的最小半徑和上一次比較獲得的最小半徑取最大值，因為要覆蓋所有的房子。
public int findRadius(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
int result = Integer.MIN_VALUE;
Arrays.sort(houses);
Arrays.sort(heaters);
int i = 0, j = 0;
while (i < houses.length) {
while (j < heaters.length-1 && Math.abs(heaters[j+1] - houses[i]) <=
Math.abs(heaters[j] - houses[i])) {
j++;
}
result = Math.max(result, Math.abs(heaters[j] - houses[i]));
i++;
}
return result;
}
03 第二種解法
我們先將加熱器排序，然後遍歷houses中的元素，我們使用二分法找到當前房子在加熱器中的最小半徑，即當前位置的房子在對應位置的加熱器中，其左右加熱器到房子之間的最小值，然後比較所有房子的最小半徑，在其中取最大值，即最大值所代表的的半徑能夠覆蓋所有房子。
public int findRadius2(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int i=0; i<houses.length; i++) {
int rad = findOne(houses[i], heaters);
result = Math.max(result, rad);
}
return result;
}
public int findOne(int house, int[] heaters) {
int start = 0, end = heaters.length-1;
int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
while (start <= end) {
int mid = (start+end)/2;
int heater = heaters[mid];
if (house == heater) {
return 0;
} else if (house < heater) {
right = heater - house;
end = mid - 1;
} else {
left = house - heater;
start = mid + 1;
}
}
return Math.min(left, right);
}
04 第三種解法
此解法和第二種解法的思路是一致的，也是利用二分法，只是藉助Arrays類的binarySearch方法來完成。
public int findRadius3(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = -(index + 1);
}
int dis = index-1 >= 0 ? house - heaters[index-1] : Integer.MAX_VALUE;
int dis2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
result = Math.max(result, Math.min(dis, dis2));
}
return result;
}
05 小結
演算法專題目前已日更超過三個月，演算法題文章106 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！