【笔记】【矩阵的二分】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…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
