Leetcode Java_二分查找

Yake1965 2022-01-07 20:08:51 阅读数:798

leetcode java_ java 二分 查找

475. 供暖器

Leetcode
在加熱站中找到每個房屋需要的最小半徑的最大值

方法一:二分查找

class Solution {

public int findRadius(int[] houses, int[] heaters) {

Arrays.sort(heaters);
int res = 0, n = heaters.length;
for (int h: houses){

int left = 0, right = n;
while (left < right){

int mid = left + (right - left) / 2;
if (h > heaters[mid]) left = mid + 1;
else right = mid;
}
int dist1 = right == 0 ? Integer.MAX_VALUE : h - heaters[right - 1];
int dist2 = right == n ? Integer.MAX_VALUE : heaters[right] - h;
res = Math.max(res, Math.min(dist1, dist2));
}
return res;
}
}

方法二:滑動窗口

class Solution {

public int findRadius(int[] houses, int[] heaters) {

Arrays.sort(houses);
int n = heaters.length;
int [] heat = Arrays.copyOf(heaters, n + 2);
heat[n] = -1000000000; // Integer.MIN_VALUE 會越界,添加哨兵
heat[n + 1] = Integer.MAX_VALUE;
Arrays.sort(heat);
int i = 0, ans = 0;
for (int h: houses){

// 找 h 右邊第一個熱站(剛好 > h), i - 1 是左邊的第一個或正好是 h 
// h 後面的不可能使用 i-1 前面的熱站,所以從 i 繼續循環。 [heaters[i-1], heaters[i]] 滑動窗口 
while (heat[i] <= h) i++;
ans = Math.max(ans, Math.min(h - heat[i-1], heat[i] - h));
}
return ans;
}
}
版权声明:本文为[Yake1965]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072008505723.html