find k closest numbers problem statement and neat solution

sherxon · Aug 30, 2017 · d9bd77f · d9bd77f
1 parent ac7b45b
commit d9bd77f
Show file tree

Hide file tree

Showing 3 changed files with 45 additions and 0 deletions.
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -1705,3 +1705,17 @@ Follow up:
 It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
 Space complexity should be O(n).
 Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
+
+145) Find K Closest Elements
+Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
+
+Example 1:
+Input: [1,2,3,4,5], k=4, x=3
+Output: [1,2,3,4]
+Example 2:
+Input: [1,2,3,4,5], k=4, x=-1
+Output: [1,2,3,4]
+Note:
+The value k is positive and will always be smaller than the length of the sorted array.
+Length of the given array is positive and will not exceed 104
+Absolute value of elements in the array and x will not exceed 104
diff --git a/src/problems/medium/FindKClosestElements.java b/src/problems/medium/FindKClosestElements.java
@@ -0,0 +1,30 @@
+package problems.medium;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.PriorityQueue;
+
+/**
+ * @author Sherali Obidov.
+ */
+public class FindKClosestElements {
+
+    public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
+        List<Integer> list= new ArrayList<>();
+        if(arr==null || arr.size()==0 || k==0)return list;
+
+        PriorityQueue<Integer> q= new PriorityQueue<>((a, b)-> {
+            int d= (Math.abs(x-a))-(Math.abs(x-b));
+            if(d==0)return a-b;
+            return d;
+        });
+        q.addAll(arr);
+        if(q.size()<k)return list;
+        for(int i=0; i<k; i++){
+            list.add(q.remove());
+        }
+        Collections.sort(list);
+        return list;
+    }
+}
diff --git a/src/problems/medium/Permutations.java b/src/problems/medium/Permutations.java
@@ -2,6 +2,7 @@
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.PriorityQueue;
 
 /**
  * Created by sherxon on 1/12/17.