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
A:
先找到比 <= x 的最大值, 假设在index seed。 然后再看看比seed+1 的difference 是否更小。
最后再linearly probe till length k
class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int n = arr.size(); // binary search to find index with bigger value that's <= than x int start = 0, end = n-1; while(start < end){ int mid = start + (end - start)/2; if(arr[mid]>x){ end = mid-1; }else{ // start = mid, but could cause infinite loop, thus if(arr[mid+1]> x){ end = mid; }else{ start = mid+1; } } } int seed = start; // chec that it is possible that's next is closer if(seed+1 < n && abs(arr[seed+1]-x) < abs(arr[seed]-x)){ seed = seed+1; } // now linear probe to search. start = seed; end = seed; while(end - start +1 < k){ if(end==n-1){ start--; }else if(start ==0){ end++; }else{ long absLeft = abs(long(arr[start-1]) - x); long absRight = abs(long(arr[end+1]) - x); if(absLeft <= absRight){ start--; }else{ end++; } } } vector<int> res(arr.begin()+start, arr.begin()+end+1); return res; } };
错误是:
1: 在start = mid 的时候,没有考虑,if mid == start, 就会有infinite loop
2: 在while loop中,一开始,画蛇添足。加了别的停止条件了。 哎。人生啊
No comments:
Post a Comment