给一个目标数 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) 的时间复杂度

注意事项

1. k是一个非负整数，并且总是小于已排序数组的长度。
2. 给定数组的长度是正整数, 不会超过 10^410​4​​
3. 数组中元素的绝对值不会超过 10^410​4​​

输入测试数据 (每行一个参数)如何理解测试数据？

 

bool cmp(pair<int, int> a, pair<int, int> b) 
{
    if(a.second < b.second)
        return true;
    else if(a.second > b.second)
        return false;
    if(a.first < b.first)
        return true;
    return false;
	
}



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
        vector<int> ret;
        if(k == 0)
            return ret;
        unordered_map<int, int> mymap;
        int size = A.size();
        for(int i = 0; i < size; i++)
        {
            mymap[A[i]] = abs(A[i] - target);
        }
        
        vector<pair<int, int>> vc;
        for(auto mit=mymap.begin(); mit!=mymap.end(); mit++)
        {
    		vc.push_back(pair<int, int>(mit->first, mit->second));
        }
        
        sort(vc.begin(), vc.end(), cmp);
        //int count = 0;
        for(auto vit=vc.begin(); vit!=vc.end(); vit++) 
        {
		    //cout<<vit->first<<"  "<<vit->second<<endl;
		    ret.push_back(vit->first);
            if(ret.size() == k)
                break;
        }
    
        return ret;
    }
};