給定一些 points 和一個 origin，從 points 中找到 k 個離 origin 最近的點。按照距離由小到大返回。如果兩個點有相同距離，則按照x值來排序；若x值也相同，就再按照y值排序。
線上評測地址：LintCode 領釦
例1：
輸入： points = ［［4，6］，［4，7］，［4，4］，［2，5］，［1，1］］， origin = ［0， 0］， k = 3
輸出： ［［1，1］，［2，5］，［4，4］］
例2：
輸入： points = ［［0，0］，［0，9］］， origin = ［3， 1］， k = 1
輸出： ［［0，0］］
題解
使用 Heapify 的方法
heapify 時間複雜度 O（n） 然後 pop k 個點出來，時間複雜度 klogn 總共的時間複雜度 O（n+klogn）
如果 n >> k 的話，這種方法的時間複雜度是很優秀的。
public
class
Solution
{
private
Point
origin
；
private
int
size
；
/**
* @param points a list of points
* @param origin a point
* @param k an integer
* @return the k closest points
*/
public
Point
［］
kClosest
（
Point
［］
points
，
Point
origin
，
int
k
）
{
if
（
points
==
null
||
points
。
length
==
0
）
{
return
points
；
}
this
。
origin
=
origin
；
heapify
（
points
）；
// O（n）
Point
［］
results
=
new
Point
［
k
］；
// O（klogn）
for
（
int
i
=
0
；
i
<
k
；
i
++）
{
results
［
i
］
=
pop
（
points
）；
}
return
results
；
}
private
void
heapify
（
Point
［］
points
）
{
size
=
points
。
length
；
for
（
int
i
=
size
/
2
；
i
>=
0
；
i
——）
{
siftDown
（
points
，
i
）；
}
}
private
void
siftDown
（
Point
［］
points
，
int
index
）
{
while
（
index
<
size
）
{
int
left
=
index
*
2
+
1
；
int
right
=
index
*
2
+
2
；
int
min
=
index
；
if
（
left
<
size
&&
compare
（
points
［
min
］，
points
［
left
］）
>
0
）
{
min
=
left
；
}
if
（
right
<
size
&&
compare
（
points
［
min
］，
points
［
right
］）
>
0
）
{
min
=
right
；
}
if
（
index
！=
min
）
{
Point
temp
=
points
［
index
］；
points
［
index
］
=
points
［
min
］；
points
［
min
］
=
temp
；
index
=
min
；
}
else
{
break
；
}
}
}
private
Point
pop
（
Point
［］
points
）
{
Point
top
=
points
［
0
］；
points
［
0
］
=
points
［
size
-
1
］；
this
。
size
——；
siftDown
（
points
，
0
）；
return
top
；
}
private
int
compare
（
Point
a
，
Point
b
）
{
int
square
=
distanceSquare
（
a
，
origin
）
-
distanceSquare
（
b
，
origin
）；
if
（
square
！=
0
）
{
return
square
；
}
if
（
a
。
x
！=
b
。
x
）
{
return
a
。
x
-
b
。
x
；
}
return
a
。
y
-
b
。
y
；
}
private
int
distanceSquare
（
Point
a
，
Point
b
）
{
return
（
a
。
x
-
b
。
x
）
*
（
a
。
x
-
b
。
x
）
+
（
a
。
y
-
b
。
y
）
*
（
a
。
y
-
b
。
y
）；
}
}
更多題解參考：九章演算法
