LeetCode 658 Find K Closest Elements

LeetCode 658 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:

<pre><b>Input:</b> [1,2,3,4,5], k=4, x=3 <b>Output:</b> [1,2,3,4] </pre>

Example 2:

<pre><b>Input:</b> [1,2,3,4,5], k=4, x=-1 <b>Output:</b> [1,2,3,4] </pre>

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 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

题目大意：

给定一个排序数组，两个整数k和x，求数组中距离x最近的k个数字。结果应该有序，距离相同时优先选择较小的数字。

解题思路：

1. 进阶二分法找出第一个大于等于key值的元素。
2. 左右两指针搜索k个元素。

注意事项：

1. 指针不能越界
2. 根据题意，与key距离一样时，取较小元素。

Java代码：

public List<Integer> findClosestElements(int[] arr, int k, int x) {
	int upperIdx = firstEqualOrGreater(arr, x);
	int lowerIdx = upperIdx-1;
	List result = new ArrayList();
	for(int i=k;i>0;i--){
		if(lowerIdx<0)
			result.add(arr[upperIdx++]);
		else if(upperIdx>=arr.length)
			result.add(arr[lowerIdx--]);
		else if(x-arr[lowerIdx]<=arr[upperIdx]-x)
			result.add(arr[lowerIdx--]);
		else
			result.add(arr[upperIdx++]);
		
	}
	Collections.sort(result);
	return result;
}

public int firstEqualOrGreater(int[] a, int key){
	int lo = 0, hi = a.length-1;
	while(lo<=hi){
		int mid =  lo + (hi - lo) / 2;
		if(a[mid]<key)
			lo = mid+1;
		else
			hi = mid-1;
	}
	return lo;
}

算法分析：

时间复杂度为O(logn+k)，空间复杂度O(1)。