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

【笔记】【矩阵的二分】668. 乘法表中第k小的数

力扣链接:题目
参考地址:参考

思路:二分查找
把矩阵想象成一维的已排好序的数组,用二分法找第k小的数字。
在这里插入图片描述
假设m行n列,则对应一维下标范围是从1到mn,初始:
l=1; r=m
n; 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小的数

力扣链接&#xff1a;题目 参考地址&#xff1a;参考 思路&#xff1a;二分查找 把矩阵想象成一维的已排好序的数组&#xff0c;用二分法找第k小的数字。 假设m行n列&#xff0c;则对应一维下标范围是从1到mn&#xff0c;初始&#xff1a; l1; rmn; mid(lr)/2 设mid在第i行&a…...

红米手机RedNot11无法使用谷歌框架,打开游戏闪退的问题,红米手机如何开启谷歌框架

红米手机RedNot11无法使用谷歌框架&#xff0c;打开游戏闪退的问题&#xff0c; 1.问题描述2.问题原因3.解决方案3.1配置谷歌框架&#xff1a;3.1软件优化 4.附图 1.问题描述 红米手机打开安卓APP没有广告&#xff0c;直接闪退&#xff0c;无法使用谷歌框架 异常关键词中包含&…...

emqx5.6.1 数据、配置备份与迁移

EMQX 支持导入和导出的数据包括&#xff1a; EMQX 配置重写的内容&#xff1a; 认证与授权配置规则、连接器与 Sink/Source监听器、网关配置其他 EMQX 配置内置数据库 (Mnesia) 的数据 Dashboard 用户和 REST API 密钥客户端认证凭证&#xff08;内置数据库密码认证、增强认证…...

VUE3脚手架工具cli配置搭建及创建VUE工程

1、VUE的脚手架工具(CLI&#xff09; 开发大型vue的时候&#xff0c;不能通过html编写一个大型的项目&#xff0c;这个时候需要用到vue的脚手架工具 通过vue的脚手架&#xff0c;可以快速的生成vue工程 1.1、安装nodejs和npm 【下载nodejs】 https://nodejs.org/en 【安装…...

前端开发之DNS协议

上一篇&#x1f449;: 前端开发之计算机网络模型认识 文章目录 DNS协议详介绍1. DNS 协议概述2. DNS协议与TCP/UDP3. DNS查询过程4. 迭代与递归查询5. DNS记录与报文结构资源记录类型对比 6. 总结 DNS协议详介绍 1. DNS 协议概述 DNS&#xff08;Domain Name System&#xf…...

如何在 Tailwind CSS 中实现居中对齐

如何在 Tailwind CSS 中实现居中对齐&#xff1a; 1. 使用 text-center 类&#xff08;针对行内元素或行内块元素&#xff09; 这个类用于将文本或行内块元素水平居中对齐。 <div class"text-center"><span>这是一个行内元素</span> </div&g…...

【iOS】编译二进制文件说明

编译二进制文件说明 如何生成文件路径文件说明第一部分&#xff1a;.o文件第二部分&#xff1a;link第三部分&#xff1a;Segment第四部分&#xff1a;Symbol 如何生成 使用Xcode进行编译 &#xff0c;会生成二进制相关文件&#xff0c;可以更详细看产物的布局 项目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&#xff0c;如果选成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对象&#xff0c;区别于JavaBean JavaBean&#xff1a;特殊的Java类&#xff0c;容易被重用或插入到其他应用程序中去&#xff0c;通过封装属性和方法成为具有某种功能或者处理某个业务的对象 这个类必须有public的无参构造器所有属性都是private的所有属…...

24年安克创新社招入职自适应能力cata测评真题分享北森测评高频题库

第一部分&#xff1a;安克创新自适应能力cata测评 感谢您关注安克创新社会招聘&#xff0c;期待与您一起弘扬中国智造之美。 为对您做出全面的评估&#xff0c;现诚邀您参加我们的在线测评。 测评名称&#xff1a;社招-安克创新自适应能力cata测评 第二部分&#xff1a;安克…...

OpenCV中的圆形标靶检测——findCirclesGrid()(三)

前面说到cv::findCirclesGrid2()内部先使用SimpleBlobDetector进行圆斑检测,然后使用CirclesGridClusterFinder算法类执行基于层次聚类的标靶检测。如下图所示,由于噪声的影响,SimpleBlobDetector检出的标靶可能包含噪声。 而CirclesGridClusterFinder算法类会执行基…...

C++拷贝构造函数、运算符重载函数、赋值运算符重载函数、前置++和后置++重载等的介绍

文章目录 前言一、拷贝构造函数1. 概念2. 特征3. 编译器生成默认拷贝构造函数4. 拷贝构造函数典型使用场景 二、运算符重载函数三、赋值运算符重载函数1. 赋值运算符重载格式2. 赋值运算符只能重载成类的成员函数不能重载成全局函数3.编译器生成一个默认赋值运算符重载4. 运算符…...

视频智能分析平台智能边缘分析一体机视频监控业务平台区域人数不足检测算法

智能边缘分析一体机区域人数不足检测算法是一种集成了先进图像处理、目标检测、跟踪和计数等功能的算法&#xff0c;专门用于实时监测和统计指定区域内的人数&#xff0c;并在人数不足时发出警报。以下是对该算法的详细介绍&#xff1a; 一、算法概述 智能边缘分析一体机区域…...

揭秘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 …...

【云手机】数据安全如何保障?

安全办公&#xff0c;信息安全&#xff0c;这是企业使用云手机的初衷和目的&#xff0c;云手机在数据保密&#xff0c;远程办公等功能上有巨大的优势&#xff0c;也为企业提供了支持 首先就是云手机能够实现数据的集中管理和加密存储。所有办公相关的数据都存储在云端的安全服务…...

【算法专题--链表】删除排序链表中的重复元素 -- 高频面试题(图文详解,小白一看就懂!!)

目录 一、前言 二、题目描述 三、解题方法 ⭐双指针 四、总结与提炼 五、共勉 一、前言 删除排序链表中的重复元素这道题&#xff0c;可以说是--链表专题--&#xff0c;最经典的一道题&#xff0c;也是在面试中频率最高的一道题目&#xff0c;通常在面试中&#xff0…...

【ajax基础01】ajax简介

目录 一&#xff1a;ajax简介 1 什么是ajax 二&#xff1a;ajax使用 1 如何使用ajax 2 axios使用&#xff08;重点&#xff09; 三&#xff1a;案例 四&#xff1a;如何赚钱 一&#xff1a;ajax简介 1 什么是ajax AJAX&#xff08;Asynchronous JavaScript And XML &am…...

[数据集][目标检测]棉花叶子害虫检测数据集VOC+YOLO格式595张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;595 标注数量(xml文件个数)&#xff1a;595 标注数量(txt文件个数)&#xff1a;595 标注类别…...

Nominatim免费的地址解析,逆地址解析,OpenStreetMap开源地图数据【全网最全】

视频学习地址 国内的一些地址解析供应商的API都开始付费了&#xff0c;就想找个免费的地址解析和逆地址解析的应用&#xff0c;最终选择了Nominatim OpenStreetMap 文章目录 一、选型1-1、数据源1-2、地理编码引擎2-1、初尝Nominatim2-1-1、地址解析2-1-2、逆地址解析 2-2、OS…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...