【笔记】【矩阵的二分】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…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
