diff options
Diffstat (limited to 'find_k_closest_elements.py')
-rw-r--r-- | find_k_closest_elements.py | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/find_k_closest_elements.py b/find_k_closest_elements.py new file mode 100644 index 0000000..966895c --- /dev/null +++ b/find_k_closest_elements.py @@ -0,0 +1,32 @@ +# 658. Find K Closest Elements + +""" +given a sorted integer array 'arr', two integers 'k' and 'x', return the 'k' +closest integers to 'x' in the array. the result should also be sorted in +ascending order. an integer 'a' is closer to 'x' than an integer 'b' if '|a - +x| < |b - x|' or '|a - x| == |b - x|' and 'a < b'. +""" + + +class Solution(object): + def findClosestElements(self, arr, k, x): + """ + :type arr: List[int] + :type k: int + :type x: int + :rtype: List[int] + """ + l, r = 0, len(arr) - k + while l < r: + m = (l + r) / 2 + if x - arr[m] > arr[m + k] - x: + l = m + 1 + else: + r = m + return arr[l : l + k] + + +if __name__ == "__main__": + obj = Solution() + print(obj.findClosestElements(arr=[1, 2, 3, 4, 5], k=4, x=3)) + print(obj.findClosestElements(arr=[1, 2, 3, 4, 5], k=4, x=-1)) |