[LeetCode] 658. Find K Closest Elements 寻找K个最近元素
Given a sorted array, two integers k
and x
, find the k
closest elements to x
in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 104
- Absolute value of elements in the array and x will not exceed 104
这道题给我们了一个数组,还有两个变量k和x。让找数组中离x最近的k个元素,而且说明了数组是有序的,如果两个数字距离x相等的话,取较小的那个。从给定的例子可以分析出x不一定是数组中的数字,由于数组是有序的,所以最后返回的k个元素也一定是有序的,那么其实就是返回了原数组的一个长度为k的子数组,转化一下,实际上相当于在长度为n的数组中去掉 n-k 个数字,而且去掉的顺序肯定是从两头开始去,因为距离x最远的数字肯定在首尾出现。那么问题就变的明朗了,每次比较首尾两个数字跟x的距离,将距离大的那个数字删除,直到剩余的数组长度为k为止,参见代码如下:
解法一:
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> res = arr;
while (res.size() > k) {
if (x - res.front() <= res.back() - x) {
res.pop_back();
} else {
res.erase(res.begin());
}
}
return res;
}
};
下面这种解法是论坛上的高分解法,用到了二分搜索法。其实博主最开始用的方法并不是帖子中的这两个方法,虽然也是用的二分搜索法,但博主搜的是第一个不小于x的数,然后同时向左右两个方向遍历,每次取和x距离最小的数加入结果 res 中,直到取满k个为止。但是下面这种方法更加巧妙一些,二分法的判定条件做了一些改变,就可以直接找到要返回的k的数字的子数组的起始位置,感觉非常的神奇。每次比较的是 mid 位置和x的距离跟 mid+k 跟x的距离,以这两者的大小关系来确定二分法折半的方向,最后找到最近距离子数组的起始位置,参见代码如下:
解法二:
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = , right = arr.size() - k;
while (left < right) {
int mid = left + (right - left) / ;
if (x - arr[mid] > arr[mid + k] - x) left = mid + ;
else right = mid;
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/658
类似题目:
Guess Number Higher or Lower II
Find K-th Smallest Pair Distance
参考资料:
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- thinkphp-无限分类下根据任意部门获取顶级部门ID
- cocos2dx3.0的CCCallFunc、CCCallFuncN
- js中Unicode转义序列
- Android 反编译
- 第四篇 :微信公众平台开发实战Java版之完成消息接受与相应以及消息的处理
- Linux基础命令(1)
- SqlServer基础:Bit类型
- SmartWiki开发日记之Laravel缓存扩展
- sublime text编辑器删除已安装的插件
- javascript中字符串格式转化成json对象记录
- maven系列(1)-maven的介绍与安装
- MATLAB-ginput函数问题
- BAE 环境下配置 struts2 + spring + hibernate(SSH)(一)准备
- d3可视化实战00:d3的使用心得和学习资料汇总
- CocoaPods 更新慢&;swift版本适配
- day01:study HTTP协议
- 【SDOI2009】学校食堂
- Android全平台书籍
- Django组件 之中间件
- java 11 ZGC(可伸缩,低延迟的gc)
热门文章
- redis集群之Sentinel
- vue.js过度&;动画、混入&;插件
- Greenplum集群或者Postgresql出现死锁肿么办?
- Centos安装jdk1.8出现-bash: //usr/local/soft/jdk1.8.0_191/bin/javac: /lib/ld-linux.so.2: bad ELF interpreter: 没有那个文件或目录错误。
- WPF Button IsMouseOver Background
- Python【day 13】内置函数01
- AD的故事继续在Sharepoint里续演
- MySql常用操作【基础且详细(●&#39;◡&#39;●)】
- Linux open fopen fdopen
- [PHP] 最简单的权限控制设计