【笔记】【矩阵的二分】668. 乘法表中第k小的数
力扣链接:题目
参考地址:参考
思路:二分查找
把矩阵想象成一维的已排好序的数组,用二分法找第k小的数字。

假设m行n列,则对应一维下标范围是从1到mn,初始:
l=1; r=mn; mid=(l+r)/2
设mid在第i行,第j列,即mid对应的值为matrix[i][j],
注意:由于乘法表中的元素并不是线性排序的,所以不能直接用mid和k比较,这样找不出第k小具体在矩阵的哪个位置,mid并不一定在矩阵中心,所以需要每次统计mid位置实际在矩阵中有多少比他小的数。
(1)由矩阵可知,0~i-1行必然比matrix[i][j]小,假设mid是matrix[1][1],比它小的值的数量为count, 初始count=0;
即,count += 0~i-1行的值的数量 , 即mid/列数 * 列数,mid/列数得到mid所在行号

(2)此外,下面的k=i~m-1行也存在比matrix[i][j]小/等于的数:第k行(mid/k)列左边的值必然比matrix[i][j]小
——因为matrix[i][j]=i * j, j=mid/i, matrix[k][mid/k] = matrix[i][mid/i] = matrix[i][j],
而左边列数<mid/k, 所以(左边的值=k*左边列数) < (matrix[k][mid/k]=k * mid/k)= matrix[i][j]
即,count += mid/k, k=i~m-1

(3)综上,<=mid对应的矩阵值的数量为:
// 当前行之上的行肯定比mid所指值小,统计比mid所指值小的个数count += mid/n * n; // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值,也要统计for(int i=mid/n+1; i<=m; i++){ // mid/n+1是当前行// 当前行有mid/i个数比mid对应的值小count += mid/i;}
或者:
for (int i = 1; i <= m; i++) {count += Math.min(x / i, n);}
总体代码如下:
class Solution {public int findKthNumber(int m, int n, int k) {int l=1, r=m*n;// m行n列,当前行idx:mid/n+mid%n,矩阵nums[][]while(l<=r){int mid = (l+r)/2;int count = 0;// 当前行之上的行肯定比mid所指值小,统计比mid所指值小的个数count += mid/n * n; // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值,也要统计for(int i=mid/n+1; i<=m; i++){ // mid/n+1是当前行// 当前行有mid/i个数比mid对应的值小count += mid/i;}if(count<k){l = mid + 1;}else{r = mid - 1;}}return l;}
}
二分法为什么输出的数一定在乘法表里?
https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solutions/891712/guan-fang-ti-jie-yu-zi-ji-de-yi-wen-java-nxu8
相关文章:
【笔记】【矩阵的二分】668. 乘法表中第k小的数
力扣链接:题目 参考地址:参考 思路:二分查找 把矩阵想象成一维的已排好序的数组,用二分法找第k小的数字。 假设m行n列,则对应一维下标范围是从1到mn,初始: l1; rmn; mid(lr)/2 设mid在第i行&a…...
红米手机RedNot11无法使用谷歌框架,打开游戏闪退的问题,红米手机如何开启谷歌框架
红米手机RedNot11无法使用谷歌框架,打开游戏闪退的问题, 1.问题描述2.问题原因3.解决方案3.1配置谷歌框架:3.1软件优化 4.附图 1.问题描述 红米手机打开安卓APP没有广告,直接闪退,无法使用谷歌框架 异常关键词中包含&…...
emqx5.6.1 数据、配置备份与迁移
EMQX 支持导入和导出的数据包括: EMQX 配置重写的内容: 认证与授权配置规则、连接器与 Sink/Source监听器、网关配置其他 EMQX 配置内置数据库 (Mnesia) 的数据 Dashboard 用户和 REST API 密钥客户端认证凭证(内置数据库密码认证、增强认证…...
VUE3脚手架工具cli配置搭建及创建VUE工程
1、VUE的脚手架工具(CLI) 开发大型vue的时候,不能通过html编写一个大型的项目,这个时候需要用到vue的脚手架工具 通过vue的脚手架,可以快速的生成vue工程 1.1、安装nodejs和npm 【下载nodejs】 https://nodejs.org/en 【安装…...
前端开发之DNS协议
上一篇👉: 前端开发之计算机网络模型认识 文章目录 DNS协议详介绍1. DNS 协议概述2. DNS协议与TCP/UDP3. DNS查询过程4. 迭代与递归查询5. DNS记录与报文结构资源记录类型对比 6. 总结 DNS协议详介绍 1. DNS 协议概述 DNS(Domain Name System…...
如何在 Tailwind CSS 中实现居中对齐
如何在 Tailwind CSS 中实现居中对齐: 1. 使用 text-center 类(针对行内元素或行内块元素) 这个类用于将文本或行内块元素水平居中对齐。 <div class"text-center"><span>这是一个行内元素</span> </div&g…...
【iOS】编译二进制文件说明
编译二进制文件说明 如何生成文件路径文件说明第一部分:.o文件第二部分:link第三部分:Segment第四部分:Symbol 如何生成 使用Xcode进行编译 ,会生成二进制相关文件,可以更详细看产物的布局 项目Target -&…...
红队内网攻防渗透:内网渗透之内网对抗:隧道技术篇防火墙组策略FRPNPSChiselSocks代理端口映射C2上线
红队内网攻防渗透 1. 内网隧道技术1.1 Frp内网穿透C2上线1.1.1 双网内网穿透C2上线1.1.1.1 服务端配置1.1.1.2 客户端配置1.1.2 内网穿透信息收集1.1.2.1、建立Socks节点(入站没限制采用)1.1.2.2 主动转发数据(出站没限制采用)1.2 Nps内网穿透工具1.2.1 NPS内网穿透C2上线1…...
qt+halcon实战
注意建QT工程项目用的是MSVC,如果选成MinGW,则会报错 INCLUDEPATH $$PWD/include INCLUDEPATH $$PWD/include/halconcppLIBS $$PWD/lib/x64-win64/halconcpp.lib LIBS $$PWD/lib/x64-win64/halcon.lib#include "halconcpp/HalconCpp.h" #include &quo…...
Java_POJO
概念 POJO即简单的Java对象,区别于JavaBean JavaBean:特殊的Java类,容易被重用或插入到其他应用程序中去,通过封装属性和方法成为具有某种功能或者处理某个业务的对象 这个类必须有public的无参构造器所有属性都是private的所有属…...
24年安克创新社招入职自适应能力cata测评真题分享北森测评高频题库
第一部分:安克创新自适应能力cata测评 感谢您关注安克创新社会招聘,期待与您一起弘扬中国智造之美。 为对您做出全面的评估,现诚邀您参加我们的在线测评。 测评名称:社招-安克创新自适应能力cata测评 第二部分:安克…...
OpenCV中的圆形标靶检测——findCirclesGrid()(三)
前面说到cv::findCirclesGrid2()内部先使用SimpleBlobDetector进行圆斑检测,然后使用CirclesGridClusterFinder算法类执行基于层次聚类的标靶检测。如下图所示,由于噪声的影响,SimpleBlobDetector检出的标靶可能包含噪声。 而CirclesGridClusterFinder算法类会执行基…...
C++拷贝构造函数、运算符重载函数、赋值运算符重载函数、前置++和后置++重载等的介绍
文章目录 前言一、拷贝构造函数1. 概念2. 特征3. 编译器生成默认拷贝构造函数4. 拷贝构造函数典型使用场景 二、运算符重载函数三、赋值运算符重载函数1. 赋值运算符重载格式2. 赋值运算符只能重载成类的成员函数不能重载成全局函数3.编译器生成一个默认赋值运算符重载4. 运算符…...
视频智能分析平台智能边缘分析一体机视频监控业务平台区域人数不足检测算法
智能边缘分析一体机区域人数不足检测算法是一种集成了先进图像处理、目标检测、跟踪和计数等功能的算法,专门用于实时监测和统计指定区域内的人数,并在人数不足时发出警报。以下是对该算法的详细介绍: 一、算法概述 智能边缘分析一体机区域…...
揭秘MMAdapt:如何利用AI跨领域战胜新兴健康谣言?
MMAdapt: A Knowledge-Guided Multi-Source Multi-Class Domain Adaptive Framework for Early Health Misinformation Detection 论文地址: MMAdapt: A Knowledge-guided Multi-source Multi-class Domain Adaptive Framework for Early Health Misinformation Detection …...
【云手机】数据安全如何保障?
安全办公,信息安全,这是企业使用云手机的初衷和目的,云手机在数据保密,远程办公等功能上有巨大的优势,也为企业提供了支持 首先就是云手机能够实现数据的集中管理和加密存储。所有办公相关的数据都存储在云端的安全服务…...
【算法专题--链表】删除排序链表中的重复元素 -- 高频面试题(图文详解,小白一看就懂!!)
目录 一、前言 二、题目描述 三、解题方法 ⭐双指针 四、总结与提炼 五、共勉 一、前言 删除排序链表中的重复元素这道题,可以说是--链表专题--,最经典的一道题,也是在面试中频率最高的一道题目,通常在面试中࿰…...
【ajax基础01】ajax简介
目录 一:ajax简介 1 什么是ajax 二:ajax使用 1 如何使用ajax 2 axios使用(重点) 三:案例 四:如何赚钱 一:ajax简介 1 什么是ajax AJAX(Asynchronous JavaScript And XML &am…...
[数据集][目标检测]棉花叶子害虫检测数据集VOC+YOLO格式595张1类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):595 标注数量(xml文件个数):595 标注数量(txt文件个数):595 标注类别…...
Nominatim免费的地址解析,逆地址解析,OpenStreetMap开源地图数据【全网最全】
视频学习地址 国内的一些地址解析供应商的API都开始付费了,就想找个免费的地址解析和逆地址解析的应用,最终选择了Nominatim OpenStreetMap 文章目录 一、选型1-1、数据源1-2、地理编码引擎2-1、初尝Nominatim2-1-1、地址解析2-1-2、逆地址解析 2-2、OS…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
Axure零基础跟我学:展开与收回
亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...
