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
Solution #1, O(logN + K)
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { int left = findClosest(arr, x); int right = left + 1; int n = arr.length; if (left == -1) { right = k; }else if (left == n) { right = n; left = n - k - 1; }else { while (k > 0) { if (left >= 0 && right < n) { if (x - arr[left] > arr[right] - x) { right++; }else { left--; } }else if (left >= 0) { left--; }else { right++; } k--; } } left++; right--; List<Integer> rt = new ArrayList<>(); for (int i = left; i <= right; i++) { rt.add(arr[i]); } return rt; } private int findClosest(int[] arr, int x) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (mid < arr.length - 1 && arr[mid] <= x && arr[mid + 1] > x) return mid; if (arr[mid] > x) { right = mid - 1; }else { left = mid + 1; } } return left; } }
Solution #2, O(logN + K),ref:https://leetcode.com/problems/find-k-closest-elements/discuss/106419/O(log-n)-Java-1-line-O(log(n)-+-k)-Ruby
二分查找subarray的起点,用反证法可以证明此算法的正确性
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { int left = 0, right = arr.length - k; while (left < right) { int mid = (left + right) / 2; if (x - arr[mid] <= arr[mid + k] - x) { right = mid; }else { left = mid + 1; } } List<Integer> rt = new ArrayList<>(); for (int i = 0; i < k; i++) { rt.add(arr[left + i]); } return rt; } }
No comments:
Post a Comment