LeetCode 658. 找到 K 个最接近的元素

Categories:

题目描述
思路分析
1. 解法一：二分定位窗口（推荐）
相似题目

题目描述

✅ 658. 找到 K 个最接近的元素

思路分析

解法一：二分定位窗口（推荐）

核心思路：

数组有序，答案是一个长度为 k 的连续窗口。

使用二分搜索窗口左边界 left，比较 x - arr[mid] 与 arr[mid+k] - x。

若左边距离更大，则窗口右移；否则左移。

复杂度分析：

时间复杂度：O(log(n - k) + k)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

import java.util.*;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int 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;
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            res.add(arr[i]);
        }
        return res;
    }
}

func findClosestElements(arr []int, k int, x int) []int {
	left, right := 0, len(arr)-k
	for left < right {
		mid := left + (right-left)/2
		if x-arr[mid] > arr[mid+k]-x {
			left = mid + 1
		} else {
			right = mid
		}
	}

	res := make([]int, 0, k)
	for i := left; i < left+k; i++ {
		res = append(res, arr[i])
	}
	return res
}

相似题目

题目	难度	考察点
704. 二分查找	简单	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
378. 有序矩阵中第 K 小的元素	中等	二分、堆
373. 查找和最小的 K 对数字	中等	堆、双指针
719. 找出第 K 小的数对距离	困难	二分、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/55866602