Driver Usb

Given a million points x y give an O n solution to find the ks points closest to 0 0

Given a million points x y give an O n solution to find the ks points closest to 0 0

Use quick select/partial sorting to resolve.
Solution:

 static class Point {
 int x;
 int y;

 public Point(int x, int y) {
 this.x = x;
 this.y = y;
 }

 public double getDistFromCenter() {
 return Math.sqrt(x * x + y * y);
 }
 }

 public static void main(String[] args) {
 Point[] points = new Point[7];
 points[0] = new Point(0, 0);
 points[1] = new Point(1, 7);
 points[2] = new Point(2, 2);
 points[3] = new Point(2, 2);
 points[4] = new Point(3, 2);
 points[5] = new Point(1, 4);
 points[6] = new Point(1, 1);
 int k = 3;
 qSelect(points, k - 1);
 for (int i = 0; i < k; i++) {
 System.out.println("" + points[i].x + "," + points[i].y);
 }
 // Output will be
 // 0,0
 // 1,1
 // 2,2
 }

 // in-place qselect and zero-based
 static void qSelect(Point[] points, int k) {
 int l = 0;
 int h = points.length - 1;
 while (l <= h) {
 int partionInd = partition(l, h, points);
 if (partionInd == k) {
 return;
 } else if (partionInd < k) {
 l = partionInd + 1;
 } else {
 h = partionInd - 1;
 }
 }
 }

 static int partition(int l, int h, Point[] points) {
 // Random can be better
 // int p = l + new Random.nextInt(h - l + 1);
 int p = l + (h - l) / 2;
 int ind = l;
 swap(p, h, points);
 Point comparePoint = points[h];
 for (int i = l; i < h; i++) {
 if (points[i].getDistFromCenter() < comparePoint.getDistFromCenter()) {
 swap(i, ind, points);
 ind++;
 }
 }
 swap(ind, h, points);
 return ind;
 }

 static void swap(int i, int j, Point[] points) {
 Point temp = points[i];
 points[i] = points[j];
 points[j] = temp;
 }

visit link download