Medium

题目描述

给定一个排序好的数组 arr，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：

输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

提示：

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 10^4
  • 数组里的每个元素与 x 的绝对值不超过 10^4

解题思路

这道题有多种解法，我们从简单到最优逐步分析：

方法一：排序法 最直观的思路是根据与 x 的距离对数组重新排序，然后取前 k 个元素。时间复杂度 O(n log n)。

方法二：双指针法 利用数组已排序的特性，使用双指针从两端向中间收缩，每次移除距离 x 更远的元素，直到剩余 k 个元素。时间复杂度 O(n)。

方法三：二分查找法（推荐） 这是最优解法。核心思想是找到最接近 x 的 k 个连续元素的起始位置。我们可以用二分查找来确定这个起始位置，搜索范围是 [0, n-k]。

对于位置 mid，我们比较 arr[mid] 和 arr[mid+k] 与 x 的距离：

  • 如果 x - arr[mid] > arr[mid+k] - x，说明右边更接近，left = mid + 1
  • 否则说明左边更接近或相等，right = mid

这样可以在 O(log n) 时间内找到起始位置，总时间复杂度为 O(log n + k)。

代码实现

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

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k
        
        while left < right:
            mid = left + (right - left) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        
        return arr[left:left + k]

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.Length - k;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        int[] result = new int[k];
        Array.Copy(arr, left, result, 0, k);
        return result;
    }
}

var findClosestElements = function(arr, k, x) {
    let left = 0, right = arr.length - k;
    
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return arr.slice(left, left + k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
排序法O(n log n)O(1)
双指针法O(n)O(1)
二分查找法O(log n + k)O(1)

推荐使用二分查找法，因为它充分利用了数组已排序的特性，时间复杂度最优。

相关题目