@compton_scatter how about this case:
1 0 1
0 1 0
1 0 1
maybe your solution is correct, but it is not same as number of connected components
@compton_scatter how about this case:
1 0 1
0 1 0
1 0 1
maybe your solution is correct, but it is not same as number of connected components
@StefanPochmann hypot is expensive when doing sqrt, which is unnecessary.
if you want to test n bucket, you just have to test n-1 bucket, so in your first example, 5*5 can test 26 buckets. if all the 25 bucket has no poison, it must in 26th bucket.
@RainbowSecret you are using extra stack using recursive calls
int findRadius(vector<int>& houses, vector<int>& heaters) {
heaters.push_back(INT_MAX);
heaters.push_back(INT_MIN);
sort(heaters.begin(), heaters.end());
long long res = 0;
for (p : houses){
int p1 = lower_bound(heaters.begin(), heaters.end(), p)-heaters.begin();
int p2 = p1-1;
long long temp = min( ((long long)heaters[p1]-p), ((long long)p-heaters[p2]));
res = max(res, temp);
}
return res;
}
@morrischen2008 if Both of array are sorted, the space complexity could be constant, time complexity is O(m+n). Just use two pointers, one for each array, and do pingpong operation.
What happens if the node number is odd? Should we swap the last node with NULL?