Leetcode - unique-paths-ii
Leetcode - subtree-of-another-tree

Leetcode - k-closest-points-to-origin

violet posted @ 5 年前 in 算法 with tags Algorithm 算法 Quick Select , 676 阅读

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.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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
Small_feed 评论 (2)
1
[回复]
DPE Result dinajpur 说:
3 年前

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.

2
[回复]
AP SSC Hindi Model P 说:
3 年前

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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter