国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] K Closest Points

沈儉 / 666人閱讀

Problem

Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.

Example

Given points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
return [[1,1],[2,5],[4,4]]

Solution
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */


public class Solution {
    /*
     * @param points: a list of points
     * @param origin: a point
     * @param k: An integer
     * @return: the k closest points
     */
    public Point[] kClosest(Point[] points, Point origin, int k) {
        Comparator pointComparator = new Comparator() {
            public int compare(Point A, Point B) {
                if (distance(B, origin) == distance(A, origin)) {
                    if (A.x == B.x) {
                        return A.y - B.y;
                    } else {
                        return A.x - B.x;
                    }
                } else {
                    //maintain a min heap
                    return distance(A, origin) > distance(B, origin) ? 1 : -1;
                }
            }
        };
        
        PriorityQueue Q = new PriorityQueue(k, pointComparator);
        
        for (Point point: points) {
            Q.add(point);
        }
        Point[] res = new Point[k];
        for (int i = 0; i < k; i++) {
            res[i] = Q.poll();
        }
        return res;
    }
    
    public double distance(Point A, Point B) {
        int l = Math.abs(A.x - B.x);
        int w = Math.abs(A.y - B.y);
        return Math.sqrt(Math.pow(l, 2) + Math.pow(w, 2));
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68189.html

相關文章

  • Leetcode PHP題解--D29 973. K Closest Points to Origi

    摘要:題目鏈接題目分析給一個坐標數組,從中返回個離最近的坐標。其中,用歐幾里得距離計算。思路把距離作為數組的鍵,把對應坐標作為數組的值。用函數排序,再用函數獲取前個即可。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 973. K Closest Points to Origin 題目鏈接 973. K Closest Points to Origin 題目分析 給一個坐標數組points...

    Sanchi 評論0 收藏0
  • [LintCode/LeetCode] 3Sum Closest

    摘要:這個題和的做法基本一樣,只要在循環內計算和最接近的和,并賦值更新返回值即可。 Problem Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three intege...

    ShevaKuilin 評論0 收藏0
  • [LintCode] Max Points on a Line

    摘要:兩次循環對中第個和第個進行比較設置重復點數,相同斜率點數。內部循環每次結束后更新和點相同斜率的點的最大數目。外部循環每次更新為之前結果和本次循環所得的較大值。重點一以一個點為參照求其他點連線的斜率,不需要計算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...

    bingo 評論0 收藏0
  • [LintCode] Baseball Game

    Problem Youre now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one rounds score): Directly represents the number of points you get...

    newtrek 評論0 收藏0

發表評論

0條評論

沈儉

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<