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

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

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[0]*point[0] + point[1]*point[1]
end```
DPE Result dinajpur 说:
Sep 03, 2022 01:36:11 AM

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. DPE Result dinajpurThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.

AP SSC Hindi Model P 说:
Sep 19, 2022 12:27:12 AM

Every student of class 10 can learn Hindi easily and this is or National language, Hindi is the most important language for every student, AP SSC Hindi Model Paper and the Board of Secondary Education, Andhra Pradesh (BSEAP) class 10th of SSC students also can download the AP 10th Hindi Model Paper 2023 Pdf with Solved question paper in chapter wise for all lessons of the course as AP SSC Hindi Model Paper 2023. Every student of class 10 can learn Hindi easily and this is or National language, Hindi is the most important language for every student.

(输入验证码)
or Ctrl+Enter