【每日算法Day 83】邻居小孩一年级就会的乘法表,你会吗?

简介: LeetCode 668. 乘法表中第k小的数

题目链接


LeetCode 668. 乘法表中第k小的数[1]

题目描述



image.png

示例1

输入:m = 3, n = 3, k = 5输出:3解释:乘法表:1  2 32  4 63  6 9第5小的数字是 3 (1, 2, 2, 3, 3).

示例2


输入:m = 2, n = 3, k = 6输出:6解释:乘法表:1  2 32  4 6第6小的数字是 6 (1, 2, 2, 3, 4, 6).

说明:

image.png

题解


二分法



image.png

二分法+优化



image.png


二分法(c++)

classSolution {
public:   
intfindKthNumber(intm, intn, intk) {   
intl=1, r=m*n;     
while (l<r) {     
intmid=l+((r-l)>>1);      
if (enough(mid, m, n, k)) r=mid; 
elsel=mid+1;    
        }     
returnl;  
    }
boolenough(intx, intm, intn, intk) {  
intcnt=0;   
for (inti=1; i<=m; ++i) {   
cnt+=x/i<n?x/i:n;     
        }    
returncnt>=k; 
    }
};

二分法+优化(c++)

classSolution {
public:   
intfindKthNumber(intm, intn, intk) { 
intl=1, r=k;    
while (l<r) {  
intmid=l+((r-l)>>1);    
if (enough(mid, m<mid?m:mid, n<mid?n:mid, k)) r=mid;            elsel=mid+1;   
        }      
returnl; 
    }
boolenough(intx, intm, intn, intk) { 
intcnt=n*(x/n), d=0; 
for (inti= (x/n)+1; i<=m; i=d+1) { 
d=x/(x/i);    
cnt+= (x/i)*((d<m?d:m)-i+1);   
        }     
returncnt>=k;  
    }
};

二分法(python)

classSolution:
deffindKthNumber(self, m: int, n: int, k: int) ->int:  
defenough(x, m, n, k):    
cnt=0foriinrange(1, m+1):     
cnt+=x//iifx//i<nelsenreturncnt>=kl, r=1, m*nwhilel<r:    
mid=l+((r-l)>>1)    
ifenough(mid, m, n, k): r=midelse: l=mid+1returnl

二分法+优化(python)

classSolution: 
deffindKthNumber(self, m: int, n: int, k: int) ->int:  
defenough(x, m, n, k):   
cnt, i, d=n*(x//n), x//n+1, 0whilei<=m:   
d=x//(x//i)     
cnt+= (x//i)*((difd<melsem)-i+1)    
i=d+1returncnt>=kl, r=1, kwhilel<r:  
mid=l+((r-l)>>1)   
ifenough(mid, mifm<midelsemid, nifn<midelsemid,
k): r=midelse: l=mid+1returnl

参考资料

[1]

LeetCode 668. 乘法表中第k小的数: https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


相关文章
|
算法 C++ Python
【每日算法Day 83】邻居小孩一年级就会的乘法表,你会吗?
【每日算法Day 83】邻居小孩一年级就会的乘法表,你会吗?
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
148 68
|
3天前
|
算法
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
1天前
|
传感器 算法
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
|
3天前
|
算法 数据可视化 数据安全/隐私保护
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
31 15
|
5天前
|
传感器 算法 物联网
基于粒子群算法的网络最优节点部署优化matlab仿真
本项目基于粒子群优化(PSO)算法,实现WSN网络节点的最优部署,以最大化节点覆盖范围。使用MATLAB2022A进行开发与测试,展示了优化后的节点分布及其覆盖范围。核心代码通过定义目标函数和约束条件,利用PSO算法迭代搜索最佳节点位置,并绘制优化结果图。PSO算法灵感源于鸟群觅食行为,适用于连续和离散空间的优化问题,在通信网络、物联网等领域有广泛应用。该算法通过模拟粒子群体智慧,高效逼近最优解,提升网络性能。
|
2天前
|
机器学习/深度学习 算法 安全
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。

热门文章

最新文章