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

题目

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

我的解法

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();//二分查找获取元素下标
        int left = right - 1;
        right++;
        while(k>0){
            if(arr[left]-x<arr[right]-x){
                left--;
                k--;
            }else if(arr[left]-x>arr[right]-x){
                right++;
                k--;
            }else if(arr[left]-x=arr[right]-x){
                if(k>1){
                    left--;
                    right++;
                    k=k-2;
                }else{
                    left--;//会有问题，如果两个边界都到头了怎么办
                }
            }
        }
        }
        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
    }
};

针对这个问题，需要在每一次循环前加一个判断边界

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();//二分查找获取元素下标
        int left = right - 1;
        while(k--){
            if(left<0){
                right++;
            }else if(right>=arr.size()){
                left--;
            }else if(x-arr[left]>arr[right]-x){
                right++;
            }else{
                left--;
            }
        }
        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
    }
};

原文地址：https://blog.csdn.net/qq_43920838/article/details/143749681

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！