Labels

Tuesday, February 3, 2015

Two Closest Points to a Given Point

 Two Closest Points to a Given Point

Find the 2 points from a list that are closest to a given point. Distance is calculated using Euclidean distance.

Naive Thinking:具体题目不详,是我根据题意总结出来的。等等,这不是跟上一题k-Nearest Points to Origin是一样的吗。现在k=2,原点变成了给定点。干脆把它扩展成k-Nearest Points to a Given Point 好了。但是也没什么大变化,没什么可说的。

就这题而言,如果用两个变量....说着说着,好好地glassdoor居然维护了!看不了题目了。
就这题而言,如果用两个变量分别存当前最小距离的两个点,然后遍历一遍不就可以直接得到结果吗,O(n)的时间复杂度,很傻喔,就跟求一个数组的最小值一样,这是什么题目,这些人真是瞎贴面试题目。


public List<Point> twoClosestPointsToAGivenPoint(List<Point> list, Point given){
        if(list.size() < 2){return list;}
        List<Point> rlst = new ArrayList<Point>();
        Point first = list.get(0);
        Point second = list.get(1);
        double f_distance = dis(first, given);
        double s_distance = dis(second, given);
        for(int i = 2;i < list.size();i++){
            double distance = dis(list.get(i),given);
            if(distance < s_distance){
                if(distance < f_distance){
                    second = first;
                    s_distance = f_distance;
                    first = list.get(i);
                    f_distance = distance;
                }else{
                    second = list.get(i);
                    s_distance = distance;
                }
            }
        }
        rlst.add(first);
        rlst.add(second);
        return rlst;
    }

    private double dis(Point a, Point b){
        return Math.pow(a.x-b.x,2)+Math.pow(a.y-b.y,2);
    }

No comments:

Post a Comment