【LeetCode】最接近原点的K个点 （优先队列PriorityQueue，快速排序根据基准数分区思想(双指针法分区)）
题目：
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例：
输入：points = [[1,3],[-2,2]], K = 1
输出：[[-2,2]]
解释： (1, 3) 和原点之间的距离为sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
此方法是通过两个K长度数组，一个记录相应points二维数组的行索引，另一个记录相应行索引算出来的斜边值。对points进行行遍历，通过数组比较，和数组移动插入，最终实现两个数组中一个记录了前K个离原点最近的点的下标，另一个记录了相应的斜边值。时间复杂度是O(n*n)。此方法是自己想的，虽然可行，但是不高效而且不简洁，唉还是太菜了。
public int[][] kClosest(int[][] points, int K) {
int temp[] = new int[K];
double tempVal[] = new double[K];
int ti = 0;
for(int i=0;i<points.length;i++) {
if(ti==0) {
temp[ti] = i;
tempVal[ti++] = Math.sqrt(Math.pow(points[i][0],2)+Math.pow(points[i][1],2));
}else {
double value = Math.sqrt(Math.pow(points[i][0],2)+Math.pow(points[i][1],2));
int index;
for(index=0;index<ti;index++) {
if(value<=tempVal[index]) {
break;
}
}
if(index==ti&&ti==K)
continue;
int j;
if(ti<K)
j = ti;
else
j = ti-1;
for(;j>index;j--) {
tempVal[j] = tempVal[j-1];
temp[j] = temp[j-1];
}
tempVal[j] = value;
temp[j] = i;
if(ti<K) {
ti++;
}
}
}
int newArray[][] = new int[K][2];
for(int i=0;i<K;i++) {
newArray[i] = points[temp[i]];
}
return newArray;
}
1.快速排序法
直接调用快排函数方法，再加一个比较器(Comparator接口)实现接口匿名内部类。此方法是将所有的值都排序好序了，再来输出前K个。
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] point1, int[] point2) {
return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
}
});
return Arrays.copyOfRange(points, 0, K);
}
2.优先队列
优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序，当使用其中的add()或offer()方法给优先队列添加时它每次都会进行自动的排序，优先队列PriorityQueue可加比较器(Comparator)。
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
return array2[0] - array1[0];
}
});
for (int i = 0; i < K; ++i) {
pq.offer(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
}
int n = points.length;
for (int i = K; i < n; ++i) {
int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
if (dist < pq.peek()[0]) {
pq.poll();
pq.offer(new int[]{dist, i});
}
}
int[][] ans = new int[K][2];
for (int i = 0; i < K; ++i) {
ans[i] = points[pq.poll()[1]];
}
return ans;
}
3.快速选择（快速排序的思想）
因为此题只要求输出前K个最接近原点的坐标，无需从小到大的顺序输出，所以可以用快速排序中的基于基准数分区的思想，不断分区然后取基准数，直到取到的基准数是第K个为止。其中的分区的实现有两种方式：快慢指针与头尾指针（这两种方式者是双指针法）！
A.【快慢指针】实现分区
Random rand = new Random();
public int[][] kClosest(int[][] points, int K) {
int n = points.length;
random_select(points, 0, n - 1, K);
return Arrays.copyOfRange(points, 0, K);
}
public void random_select(int[][] points, int left, int right, int K) {
int pivotId = left + rand.nextInt(right - left + 1);
int pivot = points[pivotId][0] * points[pivotId][0] + points[pivotId][1] * points[pivotId][1];
swap(points, right, pivotId);
int i = left - 1;
for (int j = left; j < right; ++j) {
int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
if (dist <= pivot) {
++i;
swap(points, i, j);
}
}
++i;
swap(points, i, right);
if (K < i - left + 1) {
random_select(points, left, i - 1, K);
} else if (K > i - left + 1) {
random_select(points, i + 1, right, K - (i - left + 1));
}
}
public void swap(int[][] points, int index1, int index2) {
int[] temp = points[index1];
points[index1] = points[index2];
points[index2] = temp;
}
B.【头尾指针】实现分区
public Random rand = new Random();
public int[][] kClosest(int[][] points, int K){
Random_select(points,K,0,points.length-1);
return Arrays.copyOfRange(points,0,K);
}
public void Random_select(int[][] points,int K,int left,int right) {
int baseNum = left+rand.nextInt(right-left+1);
int baseVal = points[baseNum][0]*points[baseNum][0]+points[baseNum][1]*points[baseNum][1];
swap(points,baseNum,right);
int i=left;
int j=right-1;
int iVal = 0;
while(i<=j) {
iVal = points[i][0]*points[i][0]+points[i][1]*points[i][1];
if(iVal>baseVal) {
swap(points,i,j--);
continue;
}
i++;
}
swap(points,i,right);
if(i-left+1>K) {
Random_select(points,K,left,i-1);
}else if(i-left+1<K) {
Random_select(points,K-(i-left+1),i+1,right);
}
return ;
}
public void swap(int[][] points, int index1, int index2) {
int[] temp = points[index1];
points[index1] = points[index2];
points[index2] = temp;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
