中国常德/西安seo优化培训机构

题目描述

分割数组为连续子序列

思路

二分查找+双指针

假设数组长度为n，因为数组已经按升序排序，可以将arr分成两部分，前一部分所有元素[0, left]都小于x，后一部分[right, n-1]都大于等于x，left和right都通过二分查找获得。
left和right指向的元素都是各自部分最接近x的元素，可以比较left和right指向的元素获取整体最接近x的元素，如果x-arr[lef]<=arr[right]-x，则left左移，否则right右移。如果left或right越界，则不考虑该部分的元素。最后加上[left+1, right-1]的元素就是最终结果，返回答案即可。

Python实现

class Solution:def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:right = bisect_left(arr, x)left = right - 1for _ in range(k):if left < 0:right += 1elif right >= len(arr) or x - arr[left] <= arr[right] - x:left -= 1else:right += 1return arr[left + 1: right]

Java实现

class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {int right = binarySearch(arr, x);int left = right - 1;while (k-- > 0) {if (left < 0) {right++;} else if (right >= arr.length) {left--;} else if (x - arr[left] <= arr[right] - x) {left--;} else {right++;}}List<Integer> ans = new ArrayList<Integer>();for (int i = left + 1; i < right; i++) {ans.add(arr[i]);}return ans;}public int binarySearch(int[] arr, int x) {int low = 0, high = arr.length - 1;while (low < high) {int mid = low + (high - low) / 2;if (arr[mid] >= x) {high = mid;} else {low = mid + 1;}}return low;}
}

C++实现

class Solution {
public:vector<int> findClosestElements(vector<int>& arr, int k, int x) {int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();int left = right - 1;while (k--) {if (left < 0) {right++;} else if (right >= arr.size()) {left--;} else if (x - arr[left] <= arr[right] - x) {left--;} else {right++;}}return vector<int>(arr.begin()+left+1, arr.begin()+right);}
};