Added _973.java (#32)

varunu28 · fishercoder1534 · commit e8145ebe59d7 · 2019-01-13T08:57:44.000-08:00
Added _973.java
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|973|[K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_973.java) | O(nlogn) | O(K) | |Easy| Math Sort
 |970|[Powerful Integers](https://leetcode.com/problems/powerful-integers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_970.java) | O(?) | O(1) | |Easy| Math
 |966|[Vowel Spellchecker](https://leetcode.com/problems/vowel-spellchecker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_966.java) | O(hlogn) | O(n) | |Medium| Hash Table, String
 |965|[Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_965.java) | O(n) | O(h) | |Easy| DFS, recursion|
diff --git a/src/main/java/com/fishercoder/solutions/_973.java b/src/main/java/com/fishercoder/solutions/_973.java
@@ -0,0 +1,43 @@
+package com.fishercoder.solutions;
+
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+public class _973 {
+
+    public static class Solution1 {
+        public int[][] kClosest(int[][] points, int K) {
+            int[][] ans = new int[K][2];
+
+            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
+                @Override
+                public int compare(int[] o1, int[] o2) {
+                    double dist1 = getDistance(o1);
+                    double dist2 = getDistance(o2);
+
+                    if (dist1 > dist2) {
+                        return 1;
+                    } else if (dist1 < dist2) {
+                        return -1;
+                    } else {
+                        return 0;
+                    }
+                }
+            });
+
+            for (int[] point : points) {
+                pq.add(point);
+            }
+
+            for (int i=0; i<K; i++) {
+                ans[i] = pq.poll();
+            }
+
+            return ans;
+        }
+
+        private double getDistance(int[] point) {
+            return Math.sqrt(Math.pow(point[0], 2) + Math.pow(point[1], 2));
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_973Test.java b/src/test/java/com/fishercoder/_973Test.java
@@ -0,0 +1,26 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._973;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _973Test {
+    private static _973.Solution1 test;
+
+    @BeforeClass
+    public static void setUp() {
+        test = new _973.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertArrayEquals(new int[][]{{-2, 2}}, test.kClosest(new int[][]{{1, 3}, {-2, 2}}, 1));
+    }
+
+    @Test
+    public void test2() {
+        assertArrayEquals(new int[][]{{3, 3},{-2, 4}}, test.kClosest(new int[][]{{3, 3},{5, -1},{-2, 4}}, 2));
+    }
+}
