Leetcode

# 973. K Closest Points to Origin

by hooni posted Apr 15, 2020
?

#### 단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

We have a list of `points` on the plane.  Find the `K` closest points to the origin `(0, 0)`.

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

```Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
```

Example 2:

```Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
```

Note:

1. `1 <= K <= points.length <= 10000`
2. `-10000 < points[i][0] < 10000`
3. `-10000 < points[i][1] < 10000`

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

class Solution {
public int[][] kClosest(int[][] points, int K) {
HashMap<Point, Double> hmap = new HashMap<Point, Double>();

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];
Double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
hmap.put(new Point(x, y), dist);
}

//priority = -minimum
PriorityQueue<Map.Entry<Point, Double>> queue
= new PriorityQueue<>(Comparator.comparing(e -> -e.getValue()));

for(Map.Entry<Point, Double> item : hmap.entrySet()){
queue.offer(item);
if(queue.size() > K){
queue.poll();
}
}

List<Point> list = new ArrayList<Point>();
while(queue.size() > 0){
}

int[][] result = new int[list.size()][2];
for(int i=0; i<list.size(); i++){
Point p = (Point)list.get(i);
result[i][0] = p.x;
result[i][1] = p.y;
}

return result;
}
}```

```class Point{
int x;
int y;
double distance;
public Point(int x, int y){
this.x = x;
this.y = y;
this.distance = Double.MAX_VALUE;
}
public double getValue(){
return this.distance;
}
}

class Solution {
public int[][] kClosest(int[][] points, int K) {
//priority = -minimum
PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparing(e -> -e.getValue()));

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];

Point item = new Point(x, y);
item.distance = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));

queue.offer(item);
if(queue.size() > K){
queue.poll();
}
}
/*
List<Point> list = new ArrayList<Point>();
while(queue.size() > 0){
}
int[][] result = new int[list.size()][2];
for(int i=0; i<list.size(); i++){
Point p = (Point)list.get(i);
result[i][0] = p.x;
result[i][1] = p.y;
}
*/
int loop = queue.size();
int[][] result = new int[loop][2];
for(int i=0; i<loop; i++){
Point p = (Point)queue.poll();
result[i][0] = p.x;
result[i][1] = p.y;
}

return result;
}
}```

```class Solution {
public int[][] kClosest(int[][] points, int K) {
int[] dist = new int[points.length];

for(int i=0; i<points.length; i++){
//int x = points[i][0];
//int y = points[i][1];
//dist[i] = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
dist[i] = points[i][0]*points[i][0] + points[i][1]*points[i][1];
}
/*
for(int i=0; i<dist.length; i++){
for(int j=0; j<dist.length; j++){
if(dist[i] < dist[j]){
int tmp = dist[i];
dist[i] = dist[j];
dist[j] = tmp;
}
}
}
*/
Arrays.sort(dist);

int maxDist = dist[K-1];
int index = 0;

int[][] result = new int[K][2];
for(int i=0; i<points.length && index<K; i++){
int tmp = points[i][0]*points[i][0] + points[i][1]*points[i][1];
if(tmp <= maxDist){
//result[index][0] = points[i][0];
//result[index][1] = points[i][1];
//index++;
result[index++] = points[i];
}
}

return result;
}
}```

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

class Solution {
public int[][] kClosest(int[][] points, int K) {
HashMap<Point, Double> hmap = new HashMap<Point, Double>();
List<Point> list = new ArrayList<Point>();

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];
Double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
hmap.put(new Point(x, y), dist);
}

for(int i=0; i<K; i++){
Point minKey = null;
Double minValue = Double.MAX_VALUE;
for(Map.Entry item : hmap.entrySet()){
Double dist = (Double)item.getValue();
if(dist < minValue){
minKey = (Point)item.getKey();
minValue = dist;
}
}

if(minKey != null){
//hmap.put(minKey, Double.MAX_VALUE);
hmap.remove(minKey);
}
}

int[][] result = new int[list.size()][2];
for(int i=0; i<list.size(); i++){
Point p = (Point)list.get(i);
result[i][0] = p.x;
result[i][1] = p.y;
}

return result;
}
}```

```class Solution {
public int[][] kClosest(int[][] points, int K) {
int[][] result = new int[K][2];
double[] distance = new double[K];

for(int i=0; i<distance.length; i++){
distance[i] = Double.MAX_VALUE;
}

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];
double d = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));

if(d < distance[K-1]){
distance[K-1] = d;
result[K-1][0] = x;
result[K-1][1] = y;

for(int m=0; m<K-1; m++){
for(int n=m; n<K; n++){
if(distance[m] > distance[n]){
double tmpd = distance[m];
distance[m] = distance[n];
distance[n] = tmpd;

int tmpx = result[m][0];
result[m][0] = result[n][0];
result[n][0] = tmpx;

int tmpy = result[m][1];
result[m][1] = result[n][1];
result[n][1] = tmpy;
}
}
}
}
}

return result;
}
}```

```class Point{
int x;
int y;
double dist;
public Point(int x, int y, double dist){
this.x = x;
this.y = y;
this.dist = dist;
}
}

class Solution {
public int[][] kClosest(int[][] points, int K) {

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];
//double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
double dist = (x-0)*(x-0) + (y-0)*(y-0);
Point point = new Point(x, y, dist);
boolean done = false;

for(int j=0; j<K && j<list.size(); j++){
Point item = list.get(j);
if(item.dist > point.dist){
done = true;
break;
}
}
if(done == false && list.size() < K){
}

done = true;
}

int[][] result = new int[K][2];
for(int i=0; i<K && i<list.size(); i++){
Point p = list.get(i);
result[i][0] = p.x;
result[i][1] = p.y;
}

return result;
}
}```

```class Solution {
public int[][] kClosest(int[][] points, int K) {
TreeMap<Double, Point> tmap = new TreeMap<Double, Point>();

for(int i=0; i<points.length; i++){
int x = points[i][0];
int y = points[i][1];
double distance = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));

tmap.put(distance, new Point(x, y));
}

int[][] result = new int[K][2];

Set set = tmap.entrySet();
Iterator iterator = set.iterator();

for(int i=0; i<K && iterator.hasNext(); i++) {
Map.Entry item = (Map.Entry)iterator.next();
Point p = (Point)item.getValue();
result[i][0] = p.x;
result[i][1] = p.y;
}

return result;
}
}```

TreeMap은 키값으로 정렬(이진트리) 되지만 키 중복이 안됨 ㅋㅋ

거리를 키로 사용할 경우 [0,1], [1,0] 거리 같지만 둘 중 하나만 적용 됨.

1 2 3 4