【每日刷题】 找到 K 个最接近的元素

 发布日期:2019-03-22 06:29:12  阅读次数:阅读数:97  来源:
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sd4567855/article/details/86367218

day17, 找到 K 个最接近的元素

题目来源:leetcode
给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较小的那个数。

示例 1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例 2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

解答:首先,用二分查找找到最接近(或等于)x的元素的位置pos,以pos 为中心设置left = 1,right = 0, left用来表示向左的偏移量,right表示向右的偏移量,当向左/向右的位置没有越界时,比较 abs(arr[pos - left]-x) 与arr[pos+right]-x的大小,选择较小的值对应的元素进入结果向量中;如果一个方向上发生越界,则只向另外一个方向移动即可。

代码:

class Solution {
public:
    int BinSearch( vector<int>& arr, int x){
        int left = 0, right = arr.size() - 1;
        while( left < right){
            int middle = left + (right - left)/2;
            if( arr[middle] == x)
                return middle;
            else if( arr[middle] > x)
                right = middle;
            else
                left = middle + 1;
        }
        return left;
    }
    
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int pos = BinSearch( arr, x);
        vector<int> result;
     
        int number = 0, left = 1, right = 0;
        while( number < k){
            number++;
            if( pos - left >= 0 && pos + right < arr.size()){
                if( abs(arr[pos-left] - x) <= arr[pos+right] - x){
                    result.push_back( arr[pos-left]);
                    left++;
                    continue;
                }
                else{
                    result.push_back( arr[pos+right]);
                    right++;
                    continue;                    
                }
            }
            else if( pos - left < 0){
                result.push_back( arr[pos+right]);
                right++;
                continue;
            }
            else if( pos + right >= arr.size()){
                result.push_back( arr[pos-left]);
                left++;
                continue;
            }
        }
        sort( result.begin(), result.end());
        return result;
    }
};

运行结果:image.png-24.3kB


我的微信公众号

在这里插入图片描述

如果您有好的新闻与建议,欢迎点击文章投稿

    发表评论

    电子邮件地址不会被公开。

  • 内容

  • 网名