数值近邻问题

一个 无序 数组中各个数互不相同  ，a 是数组中的一个数 ，求与 a 最接近的 k 的数

1。最笨的算法 ，排序 ，然后a两边找  

2。转变思路 ，其实求所有与 a 的 绝对差的前 k 个数

则可得到 

先将数组  for( x: x[]) x=|x-a|

利用  select  算法  (算法导论  O(n) )

可以找第  k+1 小个数 :Y,则  对于原数组的数  只要他和a的绝对值小于等于  Y ,就是我们所找的数

 

 

//绝对值
x_bak=new []
for( x: x[])  {
x=|x-a|
x_bak[]=x;
}


//找到第k+1 小的数
Y=select(x_bak,k+1);

//所有差小于 y ，和a 也是 k 接近
for(x:x[])  {
x=|x-a|
if(x<=y)
result[]=x;
}

return result;