@@ -51,6 +51,45 @@ Solution using a max Heap
5151 }
5252}
5353
54+ /* *
55+ Solution using QuickSelect
56+ */
57+ class Solution {
58+ fun kClosest (points : Array <IntArray >,k : Int ):Array <IntArray > {
59+ if (points.size== k)
60+ return points
61+ val res= Array (k){IntArray (2 ) }
62+ quickSelect(0 , points.size- 1 ,points,k)
63+ for (iin res.indices){
64+ res[i]= points[i]
65+ }
66+ return res
67+ }
68+ private fun quickSelect (l : Int ,r : Int ,points : Array <IntArray >,k : Int ){
69+ var lPointer= l
70+ for (iin l until r){
71+ if (distance(i, points)<= distance(r,points)){// r is pivot
72+ swap(i,lPointer,points)
73+ lPointer++
74+ }
75+ }
76+ swap(lPointer,r,points)
77+ if (lPointer> k)
78+ quickSelect(l, lPointer- 1 , points, k)
79+ else if (lPointer< k)
80+ quickSelect(lPointer+ 1 , r, points, k)
81+ else // lPointer == k
82+ return
83+ }
84+ private fun swap (i : Int ,j : Int ,points : Array <IntArray >){
85+ val temp= points[i]
86+ points[i]= points[j]
87+ points[j]= temp
88+ }
89+ private fun distance (i : Int ,points : Array <IntArray >)= (points[i][0 ]* points[i][0 ])+ (points[i][1 ]* points[i][1 ])
90+ }
91+
92+
5493/* *
5594Solution using built in sort function
5695*/