[leetcode]658. Find K Closest Elements绝对距离最近的K个元素
2024-08-21 07:51:33
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
题目
思路
本题要求我们在sorted array中找出K个最相近于x的数。因为输出结果一定排好序的、k-size的区间,若能找出该区间的leftBound,向右边走k个值,就可以得到desired output。
即问题转化为,怎样找到该leftBound呢? 在[0, n-k]中使用binary search查找
代码
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int begin = 0;
int end = arr.length - k;
while(begin < end){
int mid = begin + (end - begin) /2 ;
if(x > arr[mid]){
if( x - arr[mid] > arr[mid + k] - x){
begin = mid +1;
}else{
end = mid;
}
}else{
end = mid;
}
}
int index = begin;
List<Integer> result = new ArrayList<>() ;
while( k != 0){
result.add(arr[index++]);
k--;
}
return result;
}
}
最新文章
- 修改oracle占用的8080端口
- 不写1行代码,在Mac上体验ASP.NET 5的最简单方法
- jQuery基础修炼圣典—DOM篇(二)jQuery遍历
- Yii2权威指南中文版及众包翻译平台
- SharePoint Server 2010 删除Web应用
- hdu3501
- app兼容性测试的几种方案
- VideoView的视频的全屏播放
- yii gridview 时间段筛选(一个输入框,自动提交,高清大图)
- appium--xpath定位元素用法
- fastjson的@JSONField注解
- 日期控件My97 DatePicker 的使用
- OKI系列针式打印机更换色带图解教程
- Bootstrap学习遇到的role属性--- 无障碍网页应用属性
- 20155210 Exp8 WEB基础实践
- get the code of function in matlab
- mysql asyn 实战
- Elasticsearch技术解析与实战(四)shard&;replica机制
- ExtJS 表单 submit时错误处理
- flight学习笔记