{"id":1814,"date":"2018-02-20T17:23:14","date_gmt":"2018-02-21T01:23:14","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1814"},"modified":"2018-09-10T03:20:14","modified_gmt":"2018-09-10T10:20:14","slug":"leetcode-786-k-th-smallest-prime-fraction","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-786-k-th-smallest-prime-fraction\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 786. K-th Smallest Prime Fraction"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 786. K-th Smallest Prime Fraction - \u5237\u9898\u627e\u5de5\u4f5c EP168\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/ZzfXmZgJ0cw?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<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u4e92\u8d28\u6570\u5b57\uff0c\u6c42\u51fa\u5b83\u4eec\u7ec4\u6210\u7684\u5206\u6570\u4e2d\u7b2cK\u5c0f\u7684\u5206\u6570\u3002<\/p>\n<p>A sorted list\u00a0<code>A<\/code>\u00a0contains 1, plus some number of primes.\u00a0 Then, for every p &lt; q in the list, we consider the fraction p\/q.<\/p>\n<p>What is the\u00a0<code>K<\/code>-th smallest fraction considered?\u00a0 Return your answer as an array of ints, where\u00a0<code>answer[0] = p<\/code>\u00a0and\u00a0<code>answer[1] = q<\/code>.<\/p>\n<pre class=\"\">Examples:\r\nInput: A = [1, 2, 3, 5], K = 3\r\nOutput: [2, 5]\r\nExplanation:\r\nThe fractions to be considered in sorted order are:\r\n1\/5, 1\/3, 2\/5, 1\/2, 3\/5, 2\/3.\r\nThe third fraction is 2\/5.\r\n\r\nInput: A = [1, 7], K = 1\r\nOutput: [1, 7]\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>A<\/code>\u00a0will have length between\u00a0<code>2<\/code>\u00a0and\u00a0<code>2000<\/code>.<\/li>\n<li>Each\u00a0<code>A[i]<\/code>\u00a0will be between\u00a0<code>1<\/code>\u00a0and\u00a0<code>30000<\/code>.<\/li>\n<li><code>K<\/code>\u00a0will be between\u00a0<code>1<\/code>\u00a0and\u00a0<code>A.length * (A.length + 1) \/ 2<\/code>.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1831\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/786-ep168.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/786-ep168.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/786-ep168-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/786-ep168-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution 1: Binary Search<\/strong><\/h1>\n<p>Binary search m, 0 &lt; m &lt; 1, such that there are exact k pairs of (i, j) that A[i] \/ A[j] &lt; m<\/p>\n<p>Time complexity: O(n*C) C &lt;= 31<\/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\r\n\/\/ Running time: 13 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; kthSmallestPrimeFraction(vector&lt;int&gt;&amp; A, int K) {\r\n    const int n = A.size();\r\n    double l = 0;\r\n    double r = 1.0;    \r\n    while (l &lt; r) {\r\n      double m = (l + r) \/ 2;\r\n      double max_f = 0.0;\r\n      int total = 0;\r\n      int p, q = 0;\r\n      for (int i = 0, j = 1; i &lt; n - 1; ++i) {\r\n        while (j &lt; n &amp;&amp; A[i] &gt; m * A[j]) ++j;\r\n        if (n == j) break;\r\n        total += (n - j);\r\n        const double f = static_cast&lt;double&gt;(A[i]) \/ A[j];\r\n        if (f &gt; max_f) {\r\n          p = i;\r\n          q = j;\r\n          max_f = f;\r\n        }\r\n      }\r\n      if (total == K)\r\n        return {A[p], A[q]};        \r\n      else if (total &gt; K)\r\n        r = m;\r\n      else\r\n        l = m;\r\n    }\r\n    return {};\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\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\n  public int[] kthSmallestPrimeFraction(int[] A, int K) {\r\n  final int n = A.length;\r\n  double l = 0;\r\n  double r = 1.0;    \r\n  while (l &lt; r) {\r\n    double m = (l + r) \/ 2;\r\n    double max_f = 0.0;\r\n    int total = 0;\r\n    int p = 0;\r\n    int q = 0;\r\n    for (int i = 0, j = 1; i &lt; n - 1; ++i) {\r\n      while (j &lt; n &amp;&amp; A[i] &gt; m * A[j]) ++j;\r\n      if (n == j) break;\r\n      total += (n - j);\r\n      final double f = (double)A[i] \/ A[j];\r\n      if (f &gt; max_f) {\r\n        p = i;\r\n        q = j;\r\n        max_f = f;\r\n      }\r\n    }\r\n    if (total == K)\r\n      return new int[]{A[p], A[q]};\r\n    else if (total &gt; K)\r\n      r = m;\r\n    else\r\n      l = m;\r\n  }\r\n  return new int[] {};\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 \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 172 ms\r\n\"\"\"\r\nclass Solution:\r\n  def kthSmallestPrimeFraction(self, A, K):\r\n    n = len(A)\r\n    l = 0.0\r\n    r = 1.0\r\n    while l &lt; r:\r\n      m = (l + r) \/ 2\r\n      max_f = 0.0\r\n      total = 0      \r\n      j = 1\r\n      for i in range(n - 1):\r\n        while j &lt; n and A[i] &gt; m * A[j]: j += 1\r\n        if j == n: break\r\n        total += n - j\r\n        f = A[i] \/ A[j]\r\n        if f &gt; max_f:\r\n          p, q, max_f = i, j, f\r\n      if total == K:\r\n        return [A[p], A[q]]\r\n      elif total &gt; K:\r\n        r = m\r\n      else:\r\n        l = m\r\n    return []<\/pre>\n<\/div><\/div>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/divide-and-conquer\/leetcode-719-find-k-th-smallest-pair-distance\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 719. Find K-th Smallest Pair Distance \u82b1\u82b1\u9171<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-668-kth-smallest-number-in-multiplication-table\/\">\u82b1\u82b1\u9171 LeetCode 668. Kth Smallest Number in Multiplication Table<\/a><\/li>\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<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u4e92\u8d28\u6570\u5b57\uff0c\u6c42\u51fa\u5b83\u4eec\u7ec4\u6210\u7684\u5206\u6570\u4e2d\u7b2cK\u5c0f\u7684\u5206\u6570\u3002 A sorted list\u00a0A\u00a0contains 1, plus some number of primes.\u00a0 Then, for every p &lt; q in the list, we consider the fraction p\/q. What&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,176],"tags":[52,217],"class_list":["post-1814","post","type-post","status-publish","format-standard","hentry","category-array","category-two-pointers","tag-binary-search","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1814","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=1814"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1814\/revisions"}],"predecessor-version":[{"id":3901,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1814\/revisions\/3901"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1814"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1814"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1814"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}