[알고리즘문제] 릿코드 K Closest Points to Origin

leetcode.com/problems/k-closest-points-to-origin/submissions/

K Closest Points to Origin - LeetCode

좌표를 가진 배열(points)과 반환 해야 되는 갯수(k)를 파라미터로 넘겨받는다.

좌표와 원점(0, 0) 사이의 거리가 가장 가까운 좌표를 반환시킨다.

√(x₁ - x₂)² + (y₁ - y₂)² 유클리디안 계산법으로 계산한다.

튜플 형태의 check 벡터를 생성하여 좌표의 절대값을 구하여 계산 후 결과와 원본 좌표를 push한다.

모든 좌표에 대한 계산이 끝난 후 원점에서 가장 가까운 좌표를 k개만큼 answer벡터에 push하여 반환한다.

Time Complexity : O(n)

Space Complexity : O(n)

impl Solution {
    pub fn k_closest(points: Vec<Vec<i32>>, mut k: i32) -> Vec<Vec<i32>> {
        let mut answer = Vec::new();
        if k == 0 { return answer; }
        let mut check = Vec::new();
        for i in 0..points.len(){
            let (mut x, mut y) = (0, 0);
            if points[i][0] < 0 { x = -points[i][0]; }
            else { x = points[i][0]; }
            if points[i][1] < 0 { y = -points[i][1]; }
            else { y = points[i][1]; }
            let result = x.pow(2) + y.pow(2);
            check.push((result, vec![points[i][0], points[i][1]]));
        }
        check.sort();
        for i in 0..k{
            answer.push(check[i as usize].1.to_owned());
        }

        answer
    }
}