共计 1062 个字符，预计需要花费 3 分钟才能阅读完成。
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.
Example:
1 | <table class="hljs-ln"><tbody><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="1"><div class="hljs-ln-n" data-line-number="1"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="1"><span class="hljs-symbol">Input:</span> n = <span class="hljs-number">12</span>, primes = [<span class="hljs-number">2</span>,<span class="hljs-number">7</span>,<span class="hljs-number">13</span>,<span class="hljs-number">19</span>]</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="2"><div class="hljs-ln-n" data-line-number="2"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="2"><span class="hljs-symbol">Output:</span> <span class="hljs-number">32</span> </td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="3"><div class="hljs-ln-n" data-line-number="3"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="3"><span class="hljs-symbol">Explanation:</span> [<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">4</span>,<span class="hljs-number">7</span>,<span class="hljs-number">8</span>,<span class="hljs-number">13</span>,<span class="hljs-number">14</span>,<span class="hljs-number">16</span>,<span class="hljs-number">19</span>,<span class="hljs-number">26</span>,<span class="hljs-number">28</span>,<span class="hljs-number">32</span>] <span class="hljs-built_in">is</span> the sequence <span class="hljs-keyword">of</span> the first <span class="hljs-number">12</span> super ugly numbers given primes = [<span class="hljs-number">2</span>,<span class="hljs-number">7</span>,<span class="hljs-number">13</span>,<span class="hljs-number">19</span>] <span class="hljs-keyword">of</span> size <span class="hljs-number">4</span>.</td></tr></tbody></table> |
Note:
1 | <table class="hljs-ln"><tbody><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="1"><div class="hljs-ln-n" data-line-number="1"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="1"><span class="hljs-number">1</span> is a super ugly number <span class="hljs-keyword">for</span> any <span class="hljs-keyword">given</span> primes.</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="2"><div class="hljs-ln-n" data-line-number="2"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="2">The <span class="hljs-keyword">given</span> numbers in primes are in ascending order.</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="3"><div class="hljs-ln-n" data-line-number="3"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="3"><span class="hljs-number">0</span> &<span class="hljs-keyword">lt</span>; k ≤ <span class="hljs-number">100</span>, <span class="hljs-number">0</span> &<span class="hljs-keyword">lt</span>; n ≤ <span class="hljs-number">106</span>, <span class="hljs-number">0</span> &<span class="hljs-keyword">lt</span>; primes[i] &<span class="hljs-keyword">lt</span>; <span class="hljs-number">1000</span>.</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="4"><div class="hljs-ln-n" data-line-number="4"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="4">The nth super ugly number is guaranteed to fit in a <span class="hljs-number">32</span>-bit signed integer.</td></tr></tbody></table> |
难度：medium
题目：写程序找出第 n 个超级丑数。超级丑数是正整数且其公因子由给定的素数组成。
思路：同丑数，三路指针换成一组指针用数组表示。
Runtime: 11 ms, faster than 97.31% of Java online submissions for Super Ugly Number.
Memory Usage: 34.2 MB, less than 82.00% of Java online submissions for Super Ugly Number.
1 | <table class="hljs-ln"><tbody><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="1"><div class="hljs-ln-n" data-line-number="1"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="1"><span class="hljs-keyword">class</span> <span class="hljs-title class_">Solution</span> {<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-type">int</span> <span class="hljs-title">nthSuperUglyNumber</span><span class="hljs-params">(<span class="hljs-type">int</span> n, <span class="hljs-type">int</span>[] primes)</span> </span>{<span class="hljs-type">long</span>[] ugly = <span class="hljs-keyword">new</span> <span class="hljs-type">long</span>[n];</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="2"><div class="hljs-ln-n" data-line-number="2"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="2"> ugly[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>;</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="3"><div class="hljs-ln-n" data-line-number="3"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="3"> <span class="hljs-type">int</span>[] p = <span class="hljs-keyword">new</span> <span class="hljs-type">int</span>[primes.length];</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="4"><div class="hljs-ln-n" data-line-number="4"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="4"> </td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="5"><div class="hljs-ln-n" data-line-number="5"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="5"> <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i < n; i++) {<span class="hljs-type">long</span> minVal = primes[<span class="hljs-number">0</span>] * ugly[i - <span class="hljs-number">1</span>];</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="6"><div class="hljs-ln-n" data-line-number="6"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="6"> <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j < primes.length; j++) {<span class="hljs-type">long</span> num = ugly[p[j]] * primes[j];</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="7"><div class="hljs-ln-n" data-line-number="7"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="7"> <span class="hljs-keyword">if</span> (num < minVal) {minVal = num;}</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="8"><div class="hljs-ln-n" data-line-number="8"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="8"> }</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="9"><div class="hljs-ln-n" data-line-number="9"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="9"> ugly[i] = minVal;</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="10"><div class="hljs-ln-n" data-line-number="10"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="10"> <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j < primes.length; j++) {<span class="hljs-keyword">if</span> (ugly[p[j]] * primes[j] == minVal) {p[j]++;</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="11"><div class="hljs-ln-n" data-line-number="11"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="11"> }</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="12"><div class="hljs-ln-n" data-line-number="12"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="12"> }</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="13"><div class="hljs-ln-n" data-line-number="13"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="13"> }</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="14"><div class="hljs-ln-n" data-line-number="14"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="14"> </td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="15"><div class="hljs-ln-n" data-line-number="15"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="15"> <span class="hljs-keyword">return</span> (<span class="hljs-type">int</span>) ugly[n - <span class="hljs-number">1</span>];</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="16"><div class="hljs-ln-n" data-line-number="16"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="16"> }</td></tr><tr><td class="hljs-ln-line hljs-ln-numbers" data-line-number="17"><div class="hljs-ln-n" data-line-number="17"></div></td><td class="hljs-ln-line hljs-ln-code" data-line-number="17">}</td></tr></tbody></table> |
正文完
