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

  • sort函数使用lambda表达式作为自定义排序函数，代码简短，时间复杂度为O(nlogn)

    • sort函数中使用lambda表达式：

      1
      2
      3
      sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
      	return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;
      })

      常用的是这四个部分：[]()->{}，分别放置：

      []：capture 子句 (C++ 规范中也称为 lambda 引入器 )，决定匿名函数中捕获哪些外部变量

      ()：参数列表 选。 (也称为 lambda 声明符)，匿名函数的参数

      ->：trailing-return-type 选，后面跟函数的返回类型

      {}：lambda 正文，函数主体

      sort函数的lambda表达式一般写法都形似上面，参数是两个int/float，函数主体就一个return语句返回一个逻辑表达式

    • 这道题的解答代码如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      class Solution {
      public:
          vector<int> findClosestElements(vector<int>& arr, int k, int x) {
              sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
                  return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;
              });
              sort(arr.begin(), arr.begin() + k);
              return vector<int>(arr.begin(), arr.begin() + k);
          }
      };

      使用自定义sort将原数组按照题目中的规则进行排序，再将符合题意的(arr.begin(), arr.begin() + k)部分按照从小到大的顺序进行排序（因为题目要求返回时按照从小到大的顺序），返回时直接return一个vector<int>(arr.begin(), arr.begin() + k);即可

  • 二分+双指针，时间复杂度只有二分和双指针移动需要的共O(logn+k)

    自己做的时候倒是第一时间想起用（笨比）双指针，但在【查找原数组中距离x最近的元素】时进行了遍历查找，复杂度较高

    • （看到有序的数组就联想）二分查找！二分查找！二分查找！可以将查找的复杂度从O(n)降低到O(logn)

      二分：关于lower_bound()和upper_bound()的常见用法

      lower_bound()和upper_bound()是默认升序排序的，此时lower_bound()找的是大于等于x的第一个元素位置，upper_bound()找的是大于x的第一个元素的位置，此时刚好就可以限出x的出现位置范围

    • （这个题中）由于返回的子数组在原数组中一定是连续的，所以双指针时也可以只保存left和right两个边界，最后再return vector<int>(arr.begin() + left + 1, arr.begin() + right);，自己做的时候找到一个元素就直接加入到ans数组里了，最后还要对ans数组进行额外的排序

  • 自己的做法是遍历查找距离的元素+笨比双指针，时间复杂度还是到了O(n+klogk)