Categorygithub.com/szhou12/leetcode-goleetcode0668-Kth-Smallest-Number-in-Multiplication-Table
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
0
Dependents
0

# README

668. Kth Smallest Number in Multiplication Table

Solution idea

Binary Search - Guess K-th Element

  • 题目的 Multiplication Table 都是正数相乘得到，所以 Sorted Table. 思路就与 378. Kth Smallest Element in a Sorted Matrix 一样

  • 小细节: 本题table是 1-indexed, 所以涉及matrix index的部分要做微小调整

Time complexity = $O((m+n)\log D)$ where $D = m*n - 1$