(双指针、二分Binary Search) leetcode 658. Find K closest Elements

题意：给定一个升序排列的数组，找到k个与x最相近的元素（即差值最小），返回的结果必须要是按升序排好的。如果有两个数与 x的差值一样，优先选择数值较小的那个数。

 

解法一：双指针（排除法），一个一个删，因为是有序数组，且返回的是连续升序子数组，所以每一次删除的元素一定是位于边界；如果数组含有共 7 个元素，要保留 3 个元素，因此要删除 4 个元素（arr.size()-k）；因为要删除的元素都位于边界，于是可以使用双指针（左指针指向数组的第一个元素，右指针指向数组最后一个元素）对撞的方式确定保留区间。

将需要删除的元素个数作为循环的条件，当right指向的元素减去x 大于或等于 left指向的元素减去x 的距离时，说明left指向的元素更接近x，故将right-1。（因为如果有两个数与 x的差值一样，优先选择数值较小的那个数）所以等于也是将right-1; 否则 left+1。

class Solution { public:vector<int> findClosestElements(vector<int>& arr, int k, int x) {int size = arr.size(), n = size-k;int left = 0, right = size-1;while(n){if(x - arr[left] <= arr[right] - x)right--;elseleft++;n--;}vector<int> a; // for(int i=left; i<=right; ++i) // a.push_back(arr[i]);a.assign(arr.begin()+left, arr.begin()+right+1);return a;} };

解法二： Binary Search

 

这道题的Binary Search 真的不好想 :(   下面是我整理的解题思路，参考了很多大神的思路（链接如下），突然发现二分搜索有好多变种啊，搞得我有点晕晕的。

 我用的两个二分搜索模板：https://www.acwing.com/blog/content/31/

对应的讲解视频：https://www.bilibili.com/video/av41422769

二分搜索github的总结贴：https://github.com/yuzhoujr/leetcode/issues/8

二分搜索的总结博客：http://blackblog.tech/2018/10/08/LeetCode2Divide/#more

youtube上讲解这道题用二分搜索的视频：https://www.youtube.com/watch?v=3ifFNvdfjyg

 

 

 

class Solution { public:vector<int> findClosestElements(vector<int>& arr, int k, int x) {int left = 0, right = arr.size()-k;while(left< right){int mid = left + (right-left)/2;if(x> arr[mid]){if(x-arr[mid] > arr[mid+k]-x)left = mid+1;elseright = mid;}elseright = mid;}return vector<int>(arr.begin()+left, arr.begin()+left+k);} };

 

转载于:https://www.cnblogs.com/Bella2017/p/11223088.html

总结

以上是生活随笔为你收集整理的(双指针、二分Binary Search) leetcode 658. Find K closest Elements的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。