LeetCode [658] Find K Closest Elements

 658. Find K Closest Elements

Medium

Given a sorted array arr, 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: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

 

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• Absolute value of elements in the array and x will not exceed 104

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { List<Integer> list = new ArrayList<>(); int n = arr.length, l = 0, r = n-1, m=0; while(l<=r){ m = (l+r)/2; if(arr[m]>=x && (m==0 || arr[m-1]<x)) break; else if(arr[m]<x) l = m+1; else r = m-1; } r = m; l = m-1; while(list.size()<k){ if(l>=0 && r<n){ if(x-arr[l]-(arr[r]-x)<=0) list.add(0, arr[l--]); else list.add(arr[r++]); }else if(l>=0) list.add(0, arr[l--]); else if(r<n) list.add(arr[r++]); } return list; } }