{"id":4590,"date":"2019-01-02T20:16:58","date_gmt":"2019-01-03T04:16:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4590"},"modified":"2019-01-02T21:13:22","modified_gmt":"2019-01-03T05:13:22","slug":"leetcode-313-super-ugly-number","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-313-super-ugly-number\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 313. Super Ugly Number"},"content":{"rendered":"\n<p>Write a program to find the&nbsp;<code>n<sup>th<\/sup><\/code>&nbsp;super ugly number.<\/p>\n\n\n\n<p>Super ugly numbers are positive numbers whose all prime factors are in the given prime list&nbsp;<code>primes<\/code>&nbsp;of size&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:<\/strong> n = 12, <code>primes<\/code> = <code>[2,7,13,19]<\/code> <br><strong>Output:<\/strong> 32  <br><strong>Explanation: <\/strong><code>[1,2,4,7,8,13,14,16,19,26,28,32] <\/code>is the sequence of the first 12               super ugly numbers given <code>primes<\/code> = <code>[2,7,13,19]<\/code> of size 4.<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1<\/code>&nbsp;is a super ugly number for any given&nbsp;<code>primes<\/code>.<\/li><li>The given numbers in&nbsp;<code>primes<\/code>&nbsp;are in ascending order.<\/li><li>0 &lt;&nbsp;<code>k<\/code>&nbsp;\u2264 100, 0 &lt;&nbsp;<code>n<\/code>&nbsp;\u2264 10<sup>6<\/sup>, 0 &lt;&nbsp;<code>primes[i]<\/code>&nbsp;&lt; 1000.<\/li><li>The n<sup>th<\/sup>&nbsp;super ugly number is guaranteed to fit in a 32-bit signed integer.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Set<\/strong><\/h2>\n\n\n\n<p>Maintain an ordered set of super ugly numbers, each time extract the smallest one, and multiply it with all primes and insert the new number into set.<\/p>\n\n\n\n<p>Time complexity: O(n*k*logn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 484 ms\nclass Solution {\npublic:\n  int nthSuperUglyNumber(int n, vector<int>& primes) {\n    if (n == 1) return 1;\n    set<int> q{begin(primes), end(primes)};        \n    for (int i = 0; i < n - 2; ++i) {      \n      auto it = begin(q);\n      int t = *it;\n      q.erase(it);\n      for (int p : primes) {\n        if (INT_MAX \/ t < p) continue;        \n        q.insert(p * t);\n      }\n      \n    }\n    return *begin(q);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Priority Queue<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 40 ms\nstruct Node {\n  int num;\n  int index;\n  int prime;\n  \n  bool operator>(const Node& o) const {\n    if (this->num == o.num) return this->index > o.index;\n    return this->num > o.num;\n  }\n};\n\nclass Solution {\npublic:\n  int nthSuperUglyNumber(int n, vector<int>& primes) {\n    if (n == 1) return 1;\n    vector<int> nums(n, 1);\n    priority_queue<Node, vector<Node>, greater<Node>> q;\n    for (int p : primes)\n      q.push({p, 1, p});\n    for (int i = 1; i < n; ++i) {\n      nums[i] = q.top().num;\n      while (nums[i] == q.top().num) {\n        Node node = std::move(q.top()); q.pop();\n        node.num = nums[node.index++] * node.prime;\n        q.push(std::move(node));\n      }\n    }    \n    return nums.back();\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Write a program to find the&nbsp;nth&nbsp;super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list&nbsp;primes&nbsp;of size&nbsp;k.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177,59,72],"class_list":["post-4590","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-prime","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4590","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=4590"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4590\/revisions"}],"predecessor-version":[{"id":4603,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4590\/revisions\/4603"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4590"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4590"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}