Find K Closest Elements
- Lintcode : 460 / Leetcode : 658
- Level : Medium
Problem
Given target, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.
Example
Example 1:
Input: A = [1, 2, 3], target = 2, k = 3
Output: [2, 1, 3]
Example 2:
Input: A = [1, 4, 6, 8], target = 3, k = 3
Output: [4, 1, 6]
Challenge
O(logn + k) time
Notice
The value k is a non-negative integer and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 10^410
4
Absolute value of elements in the array will not exceed 10^410
4
Concept & Algorithm
Time Complexity & Space Complexity
time : O(logn + k)
space: O(k)
Answer
class Solution {
public:
vector<int> kClosestNumbers(vector<int> &A, int target, int k) {
// corner case
if (A.size() < k) return A;
int index = findLastLessAndEqual(A, target);
vector<int> ans;
countK(A, target, k, ans, index);
return ans;
}
int findLastLessAndEqual (vector<int> &A, int target) {
int l = 0, r = A.size() - 1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (A[mid] <= target) {
l = mid;
}else {
r = mid;
}
}
if (A[r] <= target) return r;
if (A[l] <= target) return l;
return -1;
}
void countK(vector<int> &A, int target, int k, vector<int> &ans, int index) {
int left = index, right = index + 1;
while (k && left >= 0 && right < A.size()) {
while (k && left >= 0 && right < A.size() && abs(A[left] - target) <= abs(A[right] - target)) {
ans.push_back(A[left--]);
k--;
}
while (k && left >= 0 && right < A.size() && abs(A[left] - target) > abs(A[right] - target)) {
ans.push_back(A[right++]);
k--;
}
}
while (k && left >= 0) {
ans.push_back(A[left--]);
k--;
}
while (k && right < A.size()) {
ans.push_back(A[right++]);
k--;
}
}
};
