// TP time: O(n) space: O(1) publicstatic List<Integer> findClosestElements(int[] arr, int k, int x){ List<Integer> ans = new ArrayList<>(); int len = arr.length; int targetPos = -1; int delta = Integer.MAX_VALUE; for (int i = 0; i < len; i++) { if (Math.abs(arr[i] - x) < delta) { delta = Math.abs(arr[i] - x); targetPos = i; } }
ans.add(arr[targetPos]); k--;
int left = targetPos - 1; int right = targetPos + 1; while (k > 0) { if (left >= 0 && right < len && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) { ans.add(arr[left]); left--; k--; } elseif (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) { ans.add(arr[right]); right++; k--; } elseif (left >= 0 && right == len) { ans.add(arr[left]); left--; k--; } elseif (left < 0 && right < len) { ans.add(arr[right]); right++; k--; } }
// Sort time: O(nlogn) space: O(logn) publicstatic List<Integer> findClosestElements_sort(int[] arr, int k, int x){ List<Integer> list = new ArrayList<>(); for (int e : arr) { list.add(e); }
Collections.sort(list, new Comparator<Integer>() { @Override publicintcompare(Integer a, Integer b){ if (Math.abs(a - x) != Math.abs(b - x)) { return Math.abs(a - x) - Math.abs(b - x); }
return a - b; } });
List<Integer> ans = list.subList(0, k); Collections.sort(ans); return ans; }
public List<Integer> findClosestElements(int[] arr, int k, int x){ List<Integer> ans = new ArrayList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override publicintcompare(Integer a, Integer b){ if (Math.abs(a - x) == Math.abs(b - x)) { return a - b; } return Math.abs(a - x) - Math.abs(b - x); } });
for (int num : arr) { pq.offer(num); }
while (!pq.isEmpty() && ans.size() < k) { ans.add(pq.poll()); }
Collections.sort(ans);
return ans; }
Analysis
Time Complexity: O(nlogn+klogk)
Space Complexity: O(n)
BinarySearch
Since the array is sorted, so it’s easy to use the Binary Search method to find the closest element of x, then we start to find the other closest elements both the left and right.
// BinarySearch time: O(n) space: O(1) publicstatic List<Integer> findClosestElements_bs(int[] arr, int k, int x){ List<Integer> ans = new ArrayList<>(); int len = arr.length; int targetPos = binarySearch(arr, x); ans.add(arr[targetPos]); k--;
int left = targetPos - 1; int right = targetPos + 1; while (k > 0) { if (left >= 0 && right < len && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) { ans.add(arr[left]); left--; k--; } elseif (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) { ans.add(arr[right]); right++; k--; } elseif (left >= 0 && right == len) { ans.add(arr[left]); left--; k--; } elseif (left < 0 && right < len) { ans.add(arr[right]); right++; k--; } }
Collections.sort(ans);
return ans; }
privatestaticintbinarySearch(int[] arr, int target){ int len = arr.length; if (arr[0] >= target) { return0; } elseif (arr[len - 1] <= target) { return len - 1; }
int left = 0; int right = arr.length - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (arr[mid] <= target) { left = mid; } else { right = mid - 1; } }
// BinarySearch Opt time: O(logn+k) space: O(1) publicstatic List<Integer> findClosestElements_bs_opt(int[] arr, int k, int x){ int len = arr.length; int right = binarySearchRight(arr, x); int left = right - 1; while (k-- > 0) { if (left < 0) { right++; } elseif (right >= len) { left--; } elseif (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) { left--; } else { right++; } }
List<Integer> ans = new ArrayList<>(); for (int i = left + 1; i < right; i++) { ans.add(arr[i]); }
return ans; }
privatestaticintbinarySearchRight(int[] arr, int target){ int left = 0; int right = arr.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { left = mid + 1; } else { right = mid; } }
return right; }
Analysis
Time Complexity: O(logn+k).
Space Complexity: O(1)
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)