LeetCode Find K Closest Elements

LeetCode Find K Closest Elements

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:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

给定一个有序数组,要从中找出k个和x最接近的元素,按升序排列输出。

首先在有序数组中用二分查找找到x的lowerbound,如果lowerbound指向begin(),则取开头k个元素即可;如果lowerbound指向end(),则取末尾k个元素;否则,令left指向lowerbound-1,right指向lowerbound,每次取left、right中和x差值最小的那个数,直到取够k个为止。最后对结果数组排序。

完整代码如下:

class Solution {
public:
	vector<int> findClosestElements(vector<int>& arr, int k, int x) {
		vector<int> ans;
		int n = arr.size();
		auto it = lower_bound(arr.begin(), arr.end(), x);
		if (it == arr.begin()) {
			while (ans.size() < k) {
				ans.push_back(*it++);
			}
			return ans;
		}
		else if (it == arr.end()) {
			while (ans.size() < k) {
				ans.push_back(*--it);
			}
			return ans;
		}
		else {
			int right = it - arr.begin();
			int left = right - 1;
			int left_diff = INT_MAX, right_diff = INT_MAX;
			while (ans.size() < k) {
				if (left >= 0)left_diff = abs(arr[left] - x);
				else left_diff = INT_MAX;
				if (right < n)right_diff = abs(arr[right] - x);
				else right_diff = INT_MAX;
				if (left_diff <= right_diff) {
					ans.push_back(arr[left]);
					--left;
				}
				else {
					ans.push_back(arr[right]);
					++right;
				}
			}
		}
		sort(ans.begin(), ans.end());
		return ans;
	}
};

本代码提交AC,用时143MS。

Leave a Reply

Your email address will not be published. Required fields are marked *