力扣973. 最接近原点的 K 个点(java 排序法,大顶堆法)

2023-12-06 05:20

本文主要是介绍力扣973. 最接近原点的 K 个点(java 排序法,大顶堆法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 973. 最接近原点的 K 个点

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

给定一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点,并且是一个整数 k ,返回离原点 (0,0) 最近的 k 个点。
这里,平面上两点之间的距离是 欧几里德距离( √(x1 - x2)2 + (y1 - y2)2 )。
你可以按 任何顺序 返回答案。除了点坐标的顺序之外,答案 确保 是 唯一 的。
在这里插入图片描述
在这里插入图片描述

思路

由于本题的数据是静态的即为了获取前TOP K我们既可以利用排序法(一般较多使用快速排序,多用于处理静态数据),也可以使用(多用于处理动态的数据)的解法来解决!

排序法:

我们将每个顶点距离原点的欧几里得距离排序,取出前K小的即可(实际操作中只需要对顶点坐标的坐标差的平方和排序即刻

大顶堆解法:

1.我们创建一个大顶堆,先将前K个顶点坐标差的平方和添加进大顶堆
2.再依次计算第K + 1到N个顶点坐标差的平方和,并依次与当前大顶堆顶的元素比较,若小于当前大顶堆的堆顶元素,则更新堆顶元素为当前的顶点的坐标差的平方和

解题方法

排序法:

1.利用java内置的排序方法,并重新定义一个Comparator接口比较计算了两个点到原点的欧几里得距离的平方
2.返回前k的顶点坐标(二维数组)

大顶堆解法:

1.我们创建一个大顶堆,堆中存取一个int类型的数组,数组的下标0位置存储该顶点到原点欧几里得距离的平方,下标为1位置存储该顶点在二维数组中的一维索引
2.再依次计算第K + 1到N个顶点坐标差的平方和,并依次与当前大顶堆顶的元素比较,若小于当前大顶堆的堆顶元素,则更新堆顶元素为当前的顶点的坐标差的平方和,与该顶点在二维数组中的一维索引
3.定义二维结果数组,存储当前大顶堆的前k大个元素,并返回(具体操作看代码)

复杂度

排序法:
时间复杂度:

O ( n l o g n ) O(nlogn) O(nlogn)

空间复杂度:

O ( l o g n ) O(logn) O(logn)

大顶堆解法:
时间复杂度:

O ( n l o g k ) O(nlogk) O(nlogk)

空间复杂度:

O ( k ) O(k) O(k)

Code

排序法

class Solution {/*** Get the first k points closest to the origin using sort** @param points Vertex coordinate array* @param k      Given number* @return int[][]*/public int[][] kClosest(int[][] points, int k) {Arrays.sort(points, new Comparator<int[]>() {public int compare(int[] point1, int[] point2) {return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);}});return Arrays.copyOfRange(points, 0, k);}
}
class Solution {/*** Gets the first k vertices closest to the origin** @param points Vertex coordinate array* @param k      Given number* @return int[][]*/public int[][] kClosest(int[][] points, int k) {//Create an maxQueuePriorityQueue<int[]> maxQueue = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o2[0] - o1[0];}});//Adds the square of the Euclidean distance for the first k coordinates to the maxQueuefor (int i = 0; i < k; ++i) {maxQueue.offer(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});}int n = points.length;/*1.Add the square of the Euclidean distance from k+1 to n vertices to the maxQueue2.If the value is less than the value for the top of the maxQueue, its value is updated*/for (int i = k; i < n; ++i) {int distance = points[i][0] * points[i][0] + points[i][1] * points[i][1];if (distance < maxQueue.peek()[0]) {maxQueue.poll();maxQueue.offer(new int[]{distance, i});}}int[][] result = new int[k][2];for (int i = 0; i < k; ++i) {result[i] = points[maxQueue.poll()[1]];}return result;}
}

这篇关于力扣973. 最接近原点的 K 个点(java 排序法,大顶堆法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/460586

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一