K个最近的点
2024-08-26 20:51:40
前段时间在网上看到一些准备找工作的人会在LintCode上刷题,然后我今天上去看了一下,也打算开始做题,然后把每天做的题目和以后的优化记录下来。
2017年8月6日 21:17:27
第一题:
描述:给定一些 points
和一个 origin
,从 points
中找到 k
个离 origin
最近的点。按照距离由小到大返回。如果两个点有相同距离,则按照x值来排序;若x值也相同,就再按照y值排序。
样例:给出 points = [[4,6],[4,7],[4,4],[2,5],[1,1]]
, origin = [0, 0]
, k = 3
返回 [[1,1],[2,5],[4,4]]
下面是我的代码:
class Point
{
public int x;
public int y;
public Point() { }
public Point(int x,int y) { this.x = x;this.y = y; }
}
class Program
{
static void Main(string[] args)
{
Point[] ps=new Point[]{new Point(,),new Point(,),new Point(,) ,new Point(,),new Point(,)};
Point[] pfinal = Closest(ps, new Point(, ), );
foreach(Point p in pfinal)
{
Console.WriteLine($"({p.x},{p.y})");
}
Console.ReadKey();
}
static Point[] Closest(Point[] points,Point origin, int k)
{
Point[] plist = new Point[k];
List<int> list = new List<int>();
for(int i =;i<points.Length;i++)
{
list.Add(GetLen(points[i], origin));
}
list.Sort();
for (int i = ; i <points.Length; i++)
{
for(int j=;j<k;j++)
{
if (list[j] == GetLen(points[i], origin))
plist[j] = points[i];
}
}
return plist;
}
static int GetLen(Point p1,Point p2)//获取两点间距离
{
return Convert.ToInt32(Math.Sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}
}
前一部分的思想是使用GetLen方法获取每个点到给定点的距离,然后把距离添加到一个List集合中,然后将List使用Sort排序,输出前K个点就可以了;
但是后来发现我无法区分哪个距离是哪个点和给定点之间的距离,都想使用Dictionary了。。。
然后问了一下室友,室友提供了一个方法:将距离保存到List集合后,再次遍历所有点,判断循环时当前点到给定点的距离和前k个距离相等时,获取当前点即可。
虽然按照样例中的数据测试是对的,但是对于对称点我觉得会出现错误,所以明天有时间再更新一次!
最新文章
- HTTP学习一:HTTP基础知识
- Unsupported major.minor version 51.0解决方法
- eclipse插件egit安装使用
- Day07_面向对象第二天
- HTTP权威指南之连接管理
- Css字体中英文对照表
- Linux技巧总结(个人经验版)
- 安卓App提交应用商店时遇到的两个小问题
- 后台调用前台js方法
- django CBV基于类视图简单实例
- SpringBootWEB项目和非Web项目的全局异常捕获
- Win8系统本地连接显示为网络2
- 闪电侠第四季/全集The Flash迅雷下载
- Qt打包部署程序自动查找依赖DLL工具windeployqt
- Qt-网易云音乐界面实现-6 迷你个人中心实现
- vue中过滤器比较两个数组取相同值
- Myeclipse中java项目转换为Web项目
- opencv中矩阵计算的一些函数
- 只包含因子2 3 5的数(51NOD 1010)
- 配置p6spyLog输出sql完整日志