网站建站方式,杭州网站建设商业,电商网站如何备案,做网站的软件工程师658. 找到 K 个最接近的元素 - 力扣#xff08;LeetCode#xff09; 给定一个 排序好 的数组 arr #xff0c;两个整数 k 和 x #xff0c;从数组中找到最靠近 x#xff08;两数之差最小#xff09;的 k 个数。返回的结果必须要是按升序排好的。 整数 a 比整数 b 更接近 …658. 找到 K 个最接近的元素 - 力扣LeetCode 给定一个 排序好 的数组 arr 两个整数 k 和 x 从数组中找到最靠近 x两数之差最小的 k 个数。返回的结果必须要是按升序排好的。 整数 a 比整数 b 更接近 x 需要满足 |a - x| |b - x| 或者|a - x| |b - x| 且 a b 示例 1 输入arr [1,2,3,4,5], k 4, x 3
输出[1,2,3,4]示例 2 输入arr [1,2,3,4,5], k 4, x -1
输出[1,2,3,4]提示 1 k arr.length1 arr.length 104arr 按 升序 排列-104 arr[i], x 104 class Solution {public ListInteger findClosestElements(int[] arr, int k, int x) {ArrayListInteger ans new ArrayListInteger();int len arr.length;int left 0;int right len - 1;while(left right) {int mid (leftright)/2;if(arr[mid]x) left mid1;else right mid;}int front left-1;int tail left;for(int i 0 ; i k ; i) {if(front 0) {ans.add(arr[tail]);tail;} else if(tail len) {ans.add(arr[front]);front--;} else {if(x-arr[front] arr[tail]-x) {ans.add(arr[front]);front--;} else{ans.add(arr[tail]);tail;}}}Collections.sort(ans);return ans;}
} 每日一题今天是中等题。实际难度也不高。 读题升序排列查找。二分查找能解决。题目要求找到离x距离最近的k个数。那首先要找到x或者离x最近的数。最简单的方法就是二分先找到离x最近的数。那就先写一个二分找到距离大于x的第一个数。leftrightlenmid老几件安排上。出二分后left就是大于x的第一个数但我们要找的是距离x最近的几个数有可能大于x也有可能小于x。所以出来之后使用front来记录小于等于x的半部分tail来记录大于等于x的半部分。tailleftfrontleft-1同时要注意x不一定在数组里所以front和tail有可能不是有效的下标。需要先进行判断1如果front0说明已经没有比x小的数了。2如果rightlen就说明没有比x大的数了。由于k一定有相应解所以一旦front和tail中的一个越界了就只能往另一边找直接加数就行。3如果front和tail都有效那么就要判断谁离x比较近由于题目有距离相同时取小的要求所以等号要加在front--的这一部分代码上。找到之后放进arraylist里面返回之前对其进行排序即可。 今天这道中等题也不怎么难熟悉二分估计很快就能做出来。结果如下
