{"id":3898,"date":"2018-09-10T03:16:04","date_gmt":"2018-09-10T10:16:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3898"},"modified":"2018-09-10T20:25:03","modified_gmt":"2018-09-11T03:25:03","slug":"leetcode-668-kth-smallest-number-in-multiplication-table","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-668-kth-smallest-number-in-multiplication-table\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 668. Kth Smallest Number in Multiplication Table"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 668. Kth Smallest Number in Multiplication Table - \u5237\u9898\u627e\u5de5\u4f5c EP223\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/qvtYRm4reL4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Nearly every one have used the\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Multiplication_table\">Multiplication Table<\/a>. But could you find out the\u00a0<code>k-th<\/code>\u00a0smallest number quickly from the multiplication table?<\/p>\n<p>Given the height\u00a0<code>m<\/code>\u00a0and the length\u00a0<code>n<\/code>\u00a0of a\u00a0<code>m * n<\/code>\u00a0Multiplication Table, and a positive integer\u00a0<code>k<\/code>, you need to return the\u00a0<code>k-th<\/code>\u00a0smallest number in this table.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> m = 3, n = 3, k = 5\r\n<b>Output:<\/b> \r\n<b>Explanation:<\/b> \r\nThe Multiplication Table:\r\n1\t2\t3\r\n2\t4\t6\r\n3\t6\t9\r\n\r\nThe 5-th smallest number is 3 (1, 2, 2, 3, 3).\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> m = 2, n = 3, k = 6\r\n<b>Output:<\/b> \r\n<b>Explanation:<\/b> \r\nThe Multiplication Table:\r\n1\t2\t3\r\n2\t4\t6\r\n\r\nThe 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The\u00a0<code>m<\/code>\u00a0and\u00a0<code>n<\/code>\u00a0will be in the range [1, 30000].<\/li>\n<li>The\u00a0<code>k<\/code>\u00a0will be in the range [1, m * n]<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3903\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/668-ep223.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/668-ep223.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/668-ep223-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/668-ep223-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<h1><strong>Solution 1: Nth element (MLE)<\/strong><\/h1>\n<p>Time complexity: O(mn)<\/p>\n<p>Space complexity: O(mn)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ 59 \/ 69 test cases passed.\r\nclass Solution {\r\npublic:\r\n  int findKthNumber(int m, int n, int k) {\r\n    vector&lt;int&gt; s(m * n);\r\n    auto it = begin(s);\r\n    for (int i = 1; i &lt;= m; ++i)\r\n      for (int j = 1; j &lt;= n; ++j)\r\n        *it++ = i * j;\r\n    nth_element(begin(s), begin(s) + k - 1, end(s));\r\n    return s[k - 1];\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution2 : Binary Search<\/strong><\/h1>\n<p>Find first x such that there are k elements less or equal to x in the table.<\/p>\n<p>Time complexity: O(m*log(m*n))<\/p>\n<p>Space complexity: O(1)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, 12 ms\r\nclass Solution {\r\npublic:\r\n  int findKthNumber(int m, int n, int k) {\r\n    int l = 1;\r\n    int r = m * n + 1;\r\n    while (l &lt; r) {\r\n      int x = l + (r - l) \/ 2;\r\n      if (LEX(m, n, x) &gt;= k)\r\n        r = x;\r\n      else\r\n        l = x + 1;\r\n    }\r\n    return l;\r\n  }\r\nprivate:\r\n  \/\/ Returns # of elements in the m*n table that are &lt;= x\r\n  int LEX(int m, int n, int x) {\r\n    int count = 0;\r\n    for (int i = 1; i &lt;= m; ++i)\r\n      count += min(n, x \/ i);\r\n    return count;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua, 16 ms\r\nclass Solution {\r\n  public int findKthNumber(int m, int n, int k) {\r\n    int l = 1;\r\n    int r = m * n + 1;\r\n    while (l &lt; r) {\r\n      int x = l + (r - l) \/ 2;\r\n      if (LEX(m, n, x) &gt;= k)\r\n        r = x;\r\n      else\r\n        l = x + 1;\r\n    }\r\n    return l;\r\n  }\r\n\r\n  \/\/ Returns # of elements in the m*n table that are &lt;= x\r\n  private int LEX(int m, int n, int x) {\r\n    int count = 0;\r\n    for (int i = 1; i &lt;= m; ++i)\r\n      count += Math.min(n, x \/ i);\r\n    return count;\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true\"># Author: Huahua, 976 ms\r\nclass Solution:\r\n  def findKthNumber(self, m, n, k):\r\n    def LEX(m, n, x, k):\r\n      count = 0\r\n      for i in range(1, min(m + 1, x + 1)):\r\n        count += min(n, x \/\/ i)\r\n        if count &gt;= k: return count\r\n      return count\r\n    l = 1\r\n    r = m * n + 1\r\n    while l &lt; r:\r\n      x = l + (r - l) \/\/ 2\r\n      if LEX(m, n, x, k) &gt;= k:\r\n        r = x\r\n      else:\r\n        l = x + 1\r\n    return l<\/pre>\n<\/div><\/div>\n<h1><strong>Related\u00a0Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-378-kth-smallest-element-in-a-sorted-matrix\/\">\u82b1\u82b1\u9171 LeetCode 378. Kth Smallest Element in a Sorted Matrix<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-786-k-th-smallest-prime-fraction\/\">\u82b1\u82b1\u9171 LeetCode 786. K-th Smallest Prime Fraction<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem Nearly every one have used the\u00a0Multiplication Table. But could you find out the\u00a0k-th\u00a0smallest number quickly from the multiplication table? Given the height\u00a0m\u00a0and the length\u00a0n\u00a0of&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,217,383,216],"class_list":["post-3898","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-hard","tag-kth","tag-matrix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3898","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3898"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3898\/revisions"}],"predecessor-version":[{"id":3907,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3898\/revisions\/3907"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3898"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3898"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}