publicint[][] kClosest(int[][] points, int k) { inttargetIndex= k - 1;
intleft=0, right = points.length - 1; while (true) { intindex= partition(points, left, right); if (index < targetIndex) { left = index + 1; } elseif (index > targetIndex) { right = index - 1; } else { return Arrays.copyOf(points, k); } } }
privateintpartition(int[][] points, int left, int right) { intpivotIndex= left + ThreadLocalRandom.current().nextInt(right - left + 1); intpivotLength= getLength(points[pivotIndex]); swap(points, pivotIndex, left);
intlt= left + 1, rt = right; while (true) { while (lt <= rt && getLength(points[lt]) < pivotLength) { lt++; } while (lt <= rt && getLength(points[rt]) > pivotLength) { rt--; }
if (lt > rt) { break; }
swap(points, lt++, rt--); }
swap(points, rt, left); return rt; }
privatevoidswap(int[][] points, int i, int j) { int[] tmp = points[i]; points[i] = points[j]; points[j] = tmp; } }