ISSUE: 輸入上百萬個(gè)行星的位置， 求距離第K近的兩個(gè)行星。
Precondition:
1. star field simulation graph is planar.
2. the coordinate of star is (x, y) that is treated as a point。
3. N = 1000000
1. bucket-sort all points according to x-coordinate. get B buckets.
this is will completed in O(NlogN).
struct bucket {
int num; // number of points in this bucket.
point* points; // points in this bucket.
double x; // value of x-coordinate.
}
bck[B]; // B buckets got.
2.
struct distance {
point p1;
point p2;
double d; // distance between p1 and p2.
}
distance kdis[K]; // to record K small distance. and it's a eliminating-tree.
kdis[0 to K-1] = 0;
for(i = [0, B-2]) // O(B)
{
// check bck[i] and bck[i+1]
if(bck[i+1].x - bck[i].x >= kdis[K-1].d && kdis[K-1] != 0)
{
// there is no need to check these two buckets.
i++;
continue; // save time.
}
point* poi = bck[i].points;
for(j = [0, bck.num-1]) // O(N/B)
{
point p = poi[j];
/*
find K points in bck[i+1] near to p
with binary searching method
according to p.y.
*/
kp[K]; // K points got in bck[i+1]
for(m = [0, K-1]) // O(K)
{
distance tmp = get_distance(kp[m], p);
if(tmp.d < kdis[K-1].d)
{
kdis[K-1] = tmp;
// adjust kdis[K-1], for it's a eliminating tree.
}
}
}
}
// finally, the kdis[K-1] is the kth distance in this star graph.
// the whole processing will be completed in O(NlogN) + O(B*N/B*K).
// and SC is O(N) + O(K) = O(N).
HOW TO FIND K POINTS?
/*
find K points in bck[i+1] near to p
with binary searching method
according to p.y.
*/
it's not complecated! and could be found in O(log(N/B)).