DEV Community

faangmaster
faangmaster

Posted on

K Closest Points to Origin

Ссылка на leetcode: https://leetcode.com/problems/k-closest-points-to-origin/description/

Код решения при помощи QuickSelect:

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int start = 0;
        int end = points.length - 1;
        while (true) {
            if (start < end) {
                swap(points, start, ThreadLocalRandom.current().nextInt(start, end));
            }
            int left = start + 1;
            int right = end;
            int pivotIndex = start;
            int pivot[] = points[pivotIndex];
            double pivotDistance = distance(pivot);
            while (left <= right) {
                if (distance(points[left]) > pivotDistance && distance(points[right]) < pivotDistance) {
                    swap(points, left, right);
                    left++;
                    right--;
                }
                if (distance(points[left]) <= pivotDistance) left++;
                if (distance(points[right]) >= pivotDistance) right--;
            }
            swap(points, pivotIndex, right);
            if (right == k - 1) break;
            if (right > k - 1) {
                end = right - 1;
            } else {
                start = right + 1;
            }
        }
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i][0] = points[i][0];
            result[i][1] = points[i][1];
        }
        return result;
    }

    private double distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private void swap(int[][] points, int i, int j) {
        int tmpX = points[i][0];
        int tmpY = points[i][1];
        points[i][0] = points[j][0];
        points[i][1] = points[j][1];
        points[j][0] = tmpX;
        points[j][1] = tmpY;
    } 
}
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up