IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode每日一题——668. 乘法表中第k小的数 -> 正文阅读

[数据结构与算法]LeetCode每日一题——668. 乘法表中第k小的数

题目

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗?

给定高度m 、宽度n 的一张 m * n的乘法表,以及正整数k,你需要返回表中第k 小的数字。

示例

例 1:

输入: m = 3, n = 3, k = 5
输出: 3
解释:
乘法表:
1 2 3
2 4 6
3 6 9

第5小的数字是 3 (1, 2, 2, 3, 3).

例 2:

输入: m = 2, n = 3, k = 6
输出: 6
解释:
乘法表:
1 2 3
2 4 6

第6小的数字是 6 (1, 2, 2, 3, 4, 6)

注意:
m 和 n 的范围在 [1, 30000] 之间。
k 的范围在 [1, m * n] 之间。

思路

首先:涉及元素极多做不到遍历的二维矩阵里的第K小都可以用二分猜答案的套路,转化为“给定一个数,求矩阵中有多少个数比这个数小”,进而实现二分查找
本题题解:

  1. 与常见二分不同点在于:本题二分是把值来当作边界,而不是下标作为边界
  2. 获得在 m * n 乘法表中,找出每行有多少个值小于等于num, 其中每行的值为 i * j (i代表当前行,j代表当前列),通过 num // i 来获取每行小于等于 num 值的总个数
  3. 乘法表 m * n 最小是1,最大是m * n, 通过提前判断加速算法
  4. 由于目标值可能存在重复边界情况,需要注意不同条件的等号判定

题解

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if k == 1:
            return 1
        if k == m * n:
            return m * n
        left, right = 1, m * n
        # 二分法求值
        while left < right:
            mid = left + ((right - left) >> 2)
            if self.countsum(m, n, mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

	# 求不超过mid的值的个数
    def countsum(self, m, n, mid):
        return sum(min(mid // i, n) for i in range(1, m + 1))
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:15:41 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 23:58:27-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码