# Leetcode - k-closest-points-to-origin

violet posted @ Mar 04, 2020 06:18:19 AM in 算法 with tags Algorithm 算法 Quick Select , 367 阅读

We have a list of `points` on the plane.  Find the `K` closest points to the origin `(0, 0)`.

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

```Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
```

This is  a quick select problem.

```def k_closest(points, k)
distances = []
points.each {|p| distances << count_distance(p)}

distance = select_k(distances, 0, distances.length - 1, k)

result = []
points.each do |p|
result << p if count_distance(p) <= distance
end
return result
end

def select_k(distances, left, right, k)

if left >= right
return distances[left]
end
pivot = left
pivot = partition(distances, left, right)
if k - 1 == pivot
return distances[pivot]
end
if k - 1 < pivot
return select_k(distances, left, pivot - 1, k)
end
return select_k(distances, pivot+1, right, k)
end

def partition(distances, left, right)
if left >= right
return left
end
pivot = left
l = left+1
r = right
while true

while l <= right && distances[pivot] > distances[l]
l+=1
end
while r >= left && distances[pivot] < distances[r]
r-=1
end
if l >= r
distances[pivot], distances[r] = distances[r], distances[pivot]
return r
end
distances[l], distances[r] = distances[r], distances[l]
l += 1
r -= 1
end
end

def count_distance(point)
return point*point + point*point
end``` (输入验证码)
or Ctrl+Enter