【leetcode】【2022/8/25】658. 找到 K 个最接近的元素

问题描述：

• 给定一个排序好的数组 arr，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。
  • 返回的结果必须要是按升序排好的。
  • 满足 k <= arr.size()。
• 整数 a 比整数 b 更接近 x 需要满足：
  • |a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b。

核心思路：

• 该题最直观的思路应该就是双指针，因为是已排序数组，所以最后返回的区间必定是连续区间，于是设定双指针于数组的头部和尾部，不断缩减区间直到区间个数为 k。
  • 实际上就是比较双指针位置的两个值，哪个离 x 更远就移动哪个位置的指针。
  • 因为数组长度为 arr.size()，最后区间长度为 k，所以实际上只需要移动 arr.size() - k 次就可以得出结果。
• 二分搜索的解法则不是那么好理解，看了几个题解，都是说二分搜索找到第一个满足条件的左边界（因为区间长度固定，找到左边界就相当于找到整个区间），而需要满足的条件为 x - arr[mid] <= arr[mid+k] - x，其中 mid 为二分搜索中找的左边界。
  • 但细节方面没有太多题解能解释清楚，我自己想了很久，理解该解法需要讨论各种情况，如 x 位于 [mid, mid+k] 的右边、位于 [mid, mid+k] 之间等等，对于不同的情况，x - arr[mid] <= arr[mid+k] - x 的解释都是不一样的，所以比较麻烦，在此不展开了。

代码实现：

• 双指针解法代码实现如下：

  class Solution
  {
  public:
      vector<int> findClosestElements(vector<int>& arr, int k, int x)
      {
          int m = arr.size();
          int l = 0, r = m-1;
          for(int i = 0; i < m - k; ++i)
          {
              if(abs(x - arr[l]) > abs(x - arr[r])) // 左边差值更大
                  ++l;
              else // 右边差值更大
                  --r;
          }
          return vector<int>(arr.begin()+l, arr.begin()+l+k);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 二分搜索解法代码实现如下：【贴自评论区】

  class Solution {
  public:
      vector<int> findClosestElements(vector<int>& arr, int k, int x) {
          int left = 0;
          int right = arr.size() - k;
          while(left < right)
          {
              int mid = (left + right) / 2;
              if(x - arr[mid] > arr[mid + k] - x)
              {
                  left = mid + 1;
              }
              else
              {
                  right = mid;
              }
          }
          return vector<int>(arr.begin() + left, arr.begin() + k + left);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20