当前位置: 首页 > news >正文

378. 有序矩阵中第 K 小的元素

378. 有序矩阵中第 K 小的元素

  • 原题链接:
  • 完成情况:
  • 解题思路:
  • 参考代码:
    • __378有序矩阵中第K小的元素__直接排序
    • __378有序矩阵中第K小的元素__归并排序
    • __378有序矩阵中第K小的元素__二分查找

原题链接:

378. 有序矩阵中第 K 小的元素

https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/description/

完成情况:

在这里插入图片描述

解题思路:

参考代码:

__378有序矩阵中第K小的元素__直接排序

package 西湖算法题解___中等题;import java.util.Arrays;public class __378有序矩阵中第K小的元素__直接排序 {public int kthSmallest(int[][] matrix, int k) {/*给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。*/int rows = matrix.length;   //行rowint cols = matrix[0].length;    //列colint sorted [] = new int[rows * cols];   //组合成一排数组,进行排序int index = 0;for (int row [] : matrix){      //每次获取matrix里的int row [] 数据for (int num : row){    //同时再在每一行row[]获取到每一个数sorted[index++] = num;}}Arrays.sort(sorted);return sorted[k-1];}
}

__378有序矩阵中第K小的元素__归并排序

package 西湖算法题解___中等题;import java.util.Comparator;
import java.util.PriorityQueue;public class __378有序矩阵中第K小的元素__归并排序 {public int kthSmallest(int[][] matrix, int k) {PriorityQueue<int []> priorityQueue = new PriorityQueue<int []>(new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return a[0] - b[0];}});//--------------------------------------------------------------------------int n = matrix.length;for (int i = 0;i<n;i++){priorityQueue.offer(new int[]{matrix[i][0],i,0});}//--------------------------------------------------------------------------for (int i = 0;i<k-1;i++){int  now [] = priorityQueue.poll();if (now[2] != n -1){priorityQueue.offer(new int[]{matrix[now[1]][now[2] + 1],now[1],now[2]+1});}}return priorityQueue.poll()[0];}
}

__378有序矩阵中第K小的元素__二分查找

package 西湖算法题解___中等题;public class __378有序矩阵中第K小的元素__二分查找 {public int kthSmallest(int[][] matrix, int k) {int n = matrix.length;int left = matrix[0][0];int right = matrix[n-1][n-1];while (left < right){int mid = left + ((right - left) >> 1 ) ;if (myCheck(matrix,mid,k,n)){right = mid;}else {left = mid + 1;}}return left;}private boolean myCheck(int[][] matrix, int mid, int k, int n) {int i = n-1;int j = 0;int num = 0;while (i >= 0 && j<n){if (matrix[i][j] <= mid){num += (i+1);j++;}else {i--;}}return num >= k;}
}

相关文章:

378. 有序矩阵中第 K 小的元素

378. 有序矩阵中第 K 小的元素 原题链接&#xff1a;完成情况&#xff1a;解题思路&#xff1a;参考代码&#xff1a;__378有序矩阵中第K小的元素__直接排序__378有序矩阵中第K小的元素__归并排序__378有序矩阵中第K小的元素__二分查找 原题链接&#xff1a; 378. 有序矩阵中…...

商品首页(sass+git本地初始化)

目录 安装sass/sass-loader 首页(vue-setup) 使用git本地提交 同步远程git库 安装sass/sass-loader #安装sass npm i sass -D#安装sass-loader npm i sass-loader10.1.1 -D 首页(vue-setup) <template><view class"u-wrap"><!-- 轮播图 --><…...

Games101学习笔记 - MVP矩阵

MV矩阵&#xff08;模型视图变换&#xff09; 目的&#xff0c;把摄像机通过变换移动的世界坐标远点&#xff0c;并且朝向与Z轴的负方向相同。这个变换就是模型试图变换。 因为移动了相机&#xff0c;如果想保持正确的渲染的话&#xff0c;那么对应的物体需要要和相机保持相对…...

从零开始搭建个人博客网站(hexo框架)

1.工具及环境搭建 1&#xff09;注册GitHub并且新建一个repositories 2&#xff09;下载node.js以及Git 下载链接&#xff1a; 检验安装是否成功&#xff1a; 【注】&#xff1a;MacOS自带Git&#xff0c;可以直接在终端输入git --version进行检验 3&#xff09;新建一个…...

vue的proxy代理详解

一、proxy常用参数说明 module.exports {publicPath: "/",devServer: {proxy: {"/api": {// 代理名称 凡是使用/api开头的地址都是用此代理target: "http://1.2.3.4:5000/", // 需要代理访问的api地址changeOrigin: true, // 允许跨域请求pa…...

计算机网络 ARP协议 IP地址简述

ARP只能在一个链路或一段网络上使用...

2021年03月 Python(一级)真题解析#中国电子学会#全国青少年软件编程等级考试

一、单选题(共25题,每题2分,共50分) 第1题 下列哪个操作不能退出IDLE环境? A:Alt+F4 B:Ctrl+Q C:按ESC键 D:exit() 正确的答案是:B:Ctrl+Q 解析:在IDLE环境中,Ctrl+Q组合键没有特定的功能,不会退出IDLE环境。要退出IDLE环境,可以使用exit()函数或者quit…...

机器学习实战4-数据预处理

文章目录 数据无量纲化preprocessing.MinMaxScaler&#xff08;归一化&#xff09;导库归一化另一种写法将归一化的结果逆转 preprocessing.StandardScaler(标准化)导库实例化查看属性查看结果逆标准化 缺失值impute.SimpleImputer另一种填充写法 处理分类型特征&#xff1a;编…...

项目管理师基础之项目管理计划和项目文件

项目管理过程中&#xff0c;会使用并产生两大类文件&#xff1a;项目管理计划和项目文件。内容一般如下&#xff1a; 整个项目生命周期需要收集、分析和转化大量的数据。从各个过程收集项目数据&#xff0c;并在项目团队内共享。在各个过程中所收集的数据经过结合相关背景的分…...

【单片机】DS2431,STM32,EEPROM读取与写入

芯片介绍&#xff1a; https://qq742971636.blog.csdn.net/article/details/132164189 接线 串口结果&#xff1a; 部分代码&#xff1a; #include "sys.h" #include "DS2431.h"unsigned char serialNb[8]; unsigned char write_data[128]; unsigned cha…...

c++11 标准模板(STL)(std::basic_stringbuf)(一)

定义于头文件 <sstream> template< class CharT, class Traits std::char_traits<CharT>, class Allocator std::allocator<CharT> > class basic_stringbuf : public std::basic_streambuf<CharT, Traits> std::basic_stringbuf…...

flutter开发实战-WidgetsBinding监听页面前台后台退出状态

flutter开发实战-WidgetsBinding监听页面前台后台退出状态 在开发过程中&#xff0c;经常监听页面前台后台退出状态&#xff0c;这里用到了WidgetsBinding 一、WidgetsBinding是什么&#xff1f; WidgetsBinding是Flutter中最重要的Binding之一&#xff0c;它提供了与Widget…...

父进程等待子进程退出 / 僵尸进程孤儿进程

Q&#xff1a;父进程为什么要等待子进程退出&#xff1f; A&#xff1a;回顾创建子进程的目的&#xff0c;就是让子进程去处理一些事情&#xff0c;那么“事情干完了没有”这件事&#xff0c;父进程需要知道并收集子进程的退出状态。子进程的退出状态如果不被收集&#xff0c;…...

【LeetCode 75】第二十六题(394)字符串解码

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码运行结果&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 给我们字符串&#xff0c;让我们解码&#xff0c;那么该怎么解码呢&#xff0c;被括号【】包裹起来的字符串需要扩展成括号左边第…...

UNIX网络编程——TCP协议API 基础demo服务器代码

目录 一.TCP客户端API 1.创建套接字 2.connect连接服务器​编辑 3.send发送信息 4.recv接受信息 5.close 二.TCP服务器API 1.socket创建tcp套接字(监听套接字) 2.bind给服务器套接字绑定port,ip地址信息 3.listen监听并创建连接队列 4.accept提取客户端的连接 5.send,r…...

[保研/考研机试] KY163 素数判定 哈尔滨工业大学复试上机题 C++实现

题目链接&#xff1a; 素数判定https://www.nowcoder.com/share/jump/437195121691718831561 描述 给定一个数n&#xff0c;要求判断其是否为素数&#xff08;0,1&#xff0c;负数都是非素数&#xff09;。 输入描述&#xff1a; 测试数据有多组&#xff0c;每组输入一个数…...

iOS_crash文件的获取及符号化(解析)

文章目录 1. 使用 symbolicatecrash 解析 .ips 文件&#xff1a;2. 使用 CrashSymbolicator.py 解析 ips 文件3. 使用 atos 解析 crash 文件4. Helps4.1 .ips 文件获取4.2 .crash 文件获取4.3 获取 .dSYM 和 .app 文件4.4 使用 dwarfdump 查询 uuid 5. Tips6. 总结 1. 使用 sym…...

STM32定时器TIM控制

一、CubeMX的设置 1、新建工程&#xff0c;进行基本配置 2、配置定时器TIM2 1&#xff09;定时器计算公式&#xff1a;&#xff08;以下两条公式相同&#xff09; Tout ((ARR1) * PSC1)) / Tclk TimeOut ((Prescaler 1) * (Period 1)) / TimeClockFren Tout TimeOut&…...

网络请求中,token和cookie有什么区别

HTTP无状态&#xff0c;每次请求都要携带cookie&#xff0c;以帮助识别用户身份&#xff1b; 服务端也可以向客户端set-cookie&#xff0c;cookie大小限制为4kb&#xff1b; cookie默认有跨域限制&#xff0c;不跨域共享和传递&#xff0c;例如&#xff1a; 现代浏览器开始禁…...

Javaweb_xml

文章目录 1.xml是什么&#xff1f;2.xml的用途 1.xml是什么&#xff1f; xml 是可扩展的标记性语言 2.xml的用途 1、用来保存数据&#xff0c;而且这些数据具有自我描述性 2、它还可以做为项目或者模块的配置文件 3、还可以做为网络传输数据的格式&#xff08;现在 JSON 为主…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...