lintcode460. 在排序数组中找最接近的K个数

比眉伴天荒 2023-07-05 13:25 8阅读 0赞

给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。

样例
    样例 1:
    
    输入: A = [1, 2, 3], target = 2, k = 3
    输出: [2, 1, 3]
    样例 2:
    
    输入: A = [1, 4, 6, 8], target = 3, k = 3`在这里插入代码片`
    输出: [4, 1, 6]
    挑战
    O(logn + k) 的时间复杂度
    
    注意事项
    k是一个非负整数，并且总是小于已排序数组的长度。
    给定数组的长度是正整数, 不会超过 10^410
    4
     
    数组中元素的绝对值不会超过 10^410
    4

class Solution {
        
    public:
        /**
         * @param A: an integer array
         * @param target: An integer
         * @param k: An integer
         * @return: an integer array
         */
        
        vector<int> kClosestNumbers(vector<int> &A, int target, int k) {
        
            // write your code here
            int len=A.size();
            vector<int> res;
            if(len==0) return res;
            else if(len<k) return A;
            int l=binarysearch(A,target);
            int r=l+1;
            while(res.size()<k)
            {
        
                if(close(A,target,l,r)) res.push_back(A[l--]);
                else res.push_back(A[r++]);
            }
            return res;
        }
        bool close(vector<int>A,int target,int l,int r)
        {
        
            if(l<0) return false;
            if(r>=A.size()) return true;
            if(target-A[l]<=A[r]-target) return true;
            return false;
        }
        int binarysearch(vector<int> A,int target)
        {
        
            int left=0;
            int right=A.size()-1;
            while(left+1<right)
            {
        
                int mid=left+(right-left)/2;
                if(A[mid]>target)right=mid;
                else if(A[mid]==target) return mid;
                else left=mid;
            }
            return left;
        }
    };