LeetCode 973 TopK问题分治算法分治

【LeetCode 973 TopK问题分治算法】因为是按tag来解所以首先用的是分治法，因为可以不用按顺序输出所以根据快速排序算法将数组分成两部分，如果划分元素位置恰好等于K则返回，小于K就说明前面的都好了，从划分位置开始划分后面的数组，大于K就继续划分前面的数组
不懂leetcode怎么回事，第一次提交132ms，比直接排序还慢，第二次就变成13ms了

public int[][] kClosest(int[][] points, int K) { if (points.length <= K) return points; int[] dis = new int[points.length]; for (int i = 0; i < points.length; i++) dis[i] = points[i][0]*points[i][0] + points[i][1]*points[i][1]; solve(0, dis.length, dis, points, K); int[][] res = new int[K][2]; for (int i = 0; i < K; i++) res[i] = points[i]; return res; } public void solve(int lo, int hi, int[] dis, int[][] points, int K) { int v = par(dis, points, lo, hi); if (v == K) return; if (v > K) solve(0, v, dis, points, K); if (v < K) solve(v+1, hi, dis, points, K); } public int par(int[] dis, int[][] points, int lo, int hi) { int t = dis[lo]; int i = lo, j = hi-1; while (true) { while (i < hi-1 && dis[++i] < t); while (j > 0 && dis[j] > t)j--; if (i >= j) break; int l = dis[i]; dis[i] = dis[j]; dis[j] = l; int [] p = points[i]; points[i] = points[j]; points[j] = p; } int l = dis[lo]; dis[lo] = dis[j]; dis[j] = l; int [] p = points[lo]; points[lo] = points[j]; points[j] = p; return j; }

这是直接排序的代码

public int[][] kClosest(int[][] points, int K) { if (points.length <= K) return points; Arrays.sort(points,(int[] a, int[] b) -> ((a[0]*a[0]+a[1]*a[1]) - (b[0]*b[0]+b[1]*b[1]))); int[][] res = new int[K][2]; for (int i = 0; i < K; i++) res[i] = points[i]; return res; }