Fill in the following methods:
public interface PointsOnAPlane {
void addPoint(Point point);
Collection<Point> findNearest(Point center, int m);
}
Click
here for the original problem:
The last is always the best. Look how much time I spent on debugging this... -_-|||
This is actually very interesting. It reminds me of the Nearest Neighbor in unsupervised learning.
Anyway, basically I use a priorityQueue to store the m closest points to the center. The comparator compares the the distance between all points and the center. I use an arrayList to store all points added to the class. When calling findNearest() method, the array needs to be sorted. Since the array is sorted, the time complexity is O(nlog(n)).
import java.util.*;
public class Point {
double x;
double y;
public Point() {
this.x = 0.0;
this.y = 0.0;
}
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public boolean equals(Point p) {
return (this.x == p.x && this.y == p.y);
}
public double distanceFrom(Point p) {
return Math.sqrt(Math.pow(p.y - this.y, 2) + Math.pow(p.x - this.x, 2));
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}
public class ThisPointsOnAPlane implements PointsOnAPlane{
private ArrayList points;
public ThisPointsOnAPlane() {
points = new ArrayList();
}
public void addPoint(Point p) {
points.add(p);
}
public PriorityQueue findNearest(Point center, int m) {
if (center == null)
throw new NullPointerException("Null center!");
PointComparator pc = new PointComparator(center);
PriorityQueue nearestNeighbor = new PriorityQueue (m, pc);
if (m == 0) {
nearestNeighbor.add(center);
return nearestNeighbor;
}
Collections.sort(points, pc);
Point last = null;
for (Point p : points) {
if (p.equals(center))
continue;
if (nearestNeighbor.size() < m) {
nearestNeighbor.add(p);
last = p;
}
else {
if (p.distanceFrom(center) < last.distanceFrom(center)) {
nearestNeighbor.remove(last);
nearestNeighbor.add(p);
last = p;
}
}
}
return nearestNeighbor;
}
public String toString () {
String rst = "{ ";
for (Point p : points) {
rst += "(" + p.x + ", " + p.y +"), ";
}
rst = rst.substring(0, rst.length() - 2) + " }";
return rst;
}
private class PointComparator implements Comparator {
Point center;
public PointComparator(Point center) {
this.center = center;
//System.out.println(center.x + ", " + center.y);
}
public int compare(Point a, Point b) {
if (a.distanceFrom(center) - b.distanceFrom(center) < 0) {
return -1;
}
else if (a.distanceFrom(center) - b.distanceFrom(center) > 0) {
return 1;
}
return 0;
}
}
}
//Test class
public class NNTester {
public static void main(String[] args) {
// TODO Auto-generated method stub
ThisPointsOnAPlane tpoap = new ThisPointsOnAPlane();
tpoap.addPoint(new Point(0, 0));
tpoap.addPoint(new Point(0, 2));
tpoap.addPoint(new Point(0, 1));
tpoap.addPoint(new Point(0, 4));
tpoap.addPoint(new Point(0, 3));
tpoap.addPoint(new Point(1, 3));
tpoap.addPoint(new Point(1, 1));
tpoap.addPoint(new Point(1, 1));
Point center = new Point(0, 0);
int m = 3;
PriorityQueue nearestNeighbor = tpoap.findNearest(center, m);
for (int i = 0; i < m; i++) {
Point p = nearestNeighbor.poll();
System.out.println("(" + p.x +", " + p.y +")");
}
}
}
However, I do see there is a comment saying using
Quickselect, we can reduce the time complexity to O(n). I am gonna think about this tomorrow.
Update about Quick select method. It won't work. First, we need an extra array to store the distances to the center of all points to do quick select. And second, we need a map to store <distance, point> pairs because after swap, the order will not be the same. So even though the the time complexity can reduce to O(n), we need O(2*n) (ah.. if you want to say O(n), is fine) extra space.
And here comes third, which actually fails the method, is that map doesn't allow duplicate key - value pairs. I am not sure if there are other containers that allow me to do that, but so far, I will stick to the priority queue method. Here is the quick select code:
public ArrayList findNearest2 (Point center, int m) {
if (center == null)
throw new NullPointerException("Null center!");
ArrayList rst = new ArrayList ();
if (m == 0)
return rst;
double[] distance = new double[points.size()];
HashMap hm = new HashMap();
for (int i = 0; i < points.size(); i++) {
distance[i] = points.get(i).distanceFrom(center);
hm.put(distance[i], points.get(i));
System.out.println(points.get(i).toString() + ": " + distance[i]);
}
quickSelect(distance, 0, distance.length - 1, m + 1);
for (int i = 0; i <= m; i++) {
if (distance[i] == 0)
continue;
rst.add(hm.get(distance[i]));
}
return rst;
}
private void quickSelect(double[] array, int start, int end, int k) {
if (start > end)
return;
double pivot = array[(start + end) / 2];
int left = start;
int right = end;
while (left < right) {
if (array[left] >= pivot) {
swap(array, left, right);
right--;
}
else {
left++;
}
}
if (array[left] > pivot)
left--;
if (k - 1 == left)
return;
else if (k - 1 < left)
quickSelect(array, start, left - 1, k);
else
quickSelect(array, left + 1, end, k);
}
private void swap (double[] array, int left, int right) {
double tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
