Problem: Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or
|a - x| == |b - x| and a < b
Example:
Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]
Input: arr = [1,2,3,4,5], k = 4, x = -1 Output: [1,2,3,4]
Approach: We can use queue here. We can keep enqueuing the array elements till we have count = k. Now if we have count = k and a new elements come, we enqueue it only if this element is closer than the element at the queue's front. In that case we dequeue the front element from the queue too. In the end the elements in the queue is our answer.
The above approach works well and will solve the problem in linear time. Let's try to do little better.
We can take the advantage of the fact that the array is sorted. We can use binary search to find the index where x should be placed (x could already in the array), say the index is target_index.
Once we have the target_index, we know that the closest k elements can be the left k elements or right k elements or mix of them so we target this range [target_index - k, target_index + k - 1] and find the closest elements in it.
That's all!
Implementation in C#:
Approach 1: Using queue:
public IList<int> FindClosestElements(int[] arr, int k, int x)
{
List<int> result = new List<int>();
int length = arr?.Length ?? 0;
if (length == 0 || k == 0 || k > length)
{
return result;
}
// 2D array -> [0]: index [1] distance
Queue<int[]> queue = new Queue<int[]>();
for (int i = 0; i < arr.Length; ++i)
{
if (queue.Count < k)
{
queue.Enqueue(new int[] {i, Math.Abs(x - arr[i])});
}
else
{
if (queue.Peek()[1] > Math.Abs(x - arr[i]))
{
queue.Dequeue();
queue.Enqueue(new int[] {i, Math.Abs(x - arr[i])});
}
}
}
while (queue.Count > 0)
{
result.Add(arr[queue.Dequeue()[0]]);
}
return result;
}
Approach 2: Using Binary Search:
public IList<int> FindClosestElements(int[] arr, int k, int x)
{
int length = arr?.Length ?? 0;
List<int> result = new List<int>();
if (length == 0 || k == 0 || k > length)
{
return result;
}
if (x < arr[0])
{
this.AddArrayElementsToList(arr, result, 0, k - 1);
return result;
}
if (x > arr[length - 1])
{
this.AddArrayElementsToList(arr, result, length - k, length - 1);
return result;
}
int index = Array.BinarySearch(arr, x);
// x does not exist
if (index < 0)
{
index = ~index;
}
int low = Math.Max(0, index - k);
int high = Math.Min(length - 1, index + k - 1);
while (high - low + 1 > k)
{
if (x - arr[low] <= arr[high] - x)
{
--high;
}
else if (x - arr[low] > arr[high] - x)
{
++low;
}
}
this.AddArrayElementsToList(arr, result, low, high);
return result;
}
private void AddArrayElementsToList(int[] arr, List<int> result, int left, int right)
{
for (int i = left; i <= right; ++i)
{
result.Add(arr[i]);
}
}
Complexity: Approach 1: O(n), Approach 2: O(logn + k)
No comments:
Post a Comment