By Long Luo
This article is the solution 4 Approaches: Two Pointers, Sorting, Priority Queue and Binary Search of Problem 658. Find K Closest Elements .
Here shows 4 Approaches to slove this problem: Two Pointers, Sorting, Priority Queue and Binary Search with Two Pointers.
Two Pointers
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public static 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--; } else if (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) { ans.add(arr[right]); right++; k--; } else if (left >= 0 && right == len) { ans.add(arr[left]); left--; k--; } else if (left < 0 && right < len) { ans.add(arr[right]); right++; k--; } } Collections.sort(ans); return ans; }
Analysis
Time Complexity : O ( n + k l o g k ) O(n + klogk) O ( n + k l o g k ) .
Space Complexity : O ( n ) O(n) O ( n ) .
Sorting
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static 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 public int compare (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; }
Analysis
Time Complexity : O ( n l o g n + k l o g k ) O(nlogn + klogk) O ( n l o g n + k l o g k ) .
Space Complexity : O ( n ) O(n) O ( n ) .
Priority Queue
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 public List<Integer> findClosestElements (int [] arr, int k, int x) { List<Integer> ans = new ArrayList <>(); PriorityQueue<Integer> pq = new PriorityQueue <>(new Comparator <Integer>() { @Override public int compare (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 ( n l o g n + k l o g k ) O(nlogn+klogk) O ( n l o g n + k l o g k )
Space Complexity : O ( n ) O(n) 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 \textit{x} x , then we start to find the other closest elements both the left and right.
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 public static 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--; } else if (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) { ans.add(arr[right]); right++; k--; } else if (left >= 0 && right == len) { ans.add(arr[left]); left--; k--; } else if (left < 0 && right < len) { ans.add(arr[right]); right++; k--; } } Collections.sort(ans); return ans; } private static int binarySearch (int [] arr, int target) { int len = arr.length; if (arr[0 ] >= target) { return 0 ; } else if (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 ; } } if (Math.abs(arr[left] - target) <= Math.abs(arr[left + 1 ] - target)) { return left; } else { return left + 1 ; } }
The code is too obscure, we can just find the closest element which gt than x \textit{x} x , then use two pointers to search other k \textit{k} k elements from both sides.
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 public static 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++; } else if (right >= len) { left--; } else if (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; } private static int binarySearchRight (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 ( l o g n + k ) O(logn + k) O ( l o g n + k ) .
Space Complexity : O ( 1 ) O(1) O ( 1 )
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗