{"id":1911,"date":"2016-03-25T14:41:34","date_gmt":"2016-03-25T06:41:34","guid":{"rendered":"http:\/\/boweihe.me\/?p=1911"},"modified":"2016-03-25T14:41:34","modified_gmt":"2016-03-25T06:41:34","slug":"leetcode-264-ugly-number-ii","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1911","title":{"rendered":"LeetCode 264. Ugly Number II"},"content":{"rendered":"<p>Write a program to find the <code>n<\/code>-th ugly number.<br \/>\nUgly numbers are positive numbers whose prime factors only include <code>2, 3, 5<\/code>. For example, <code>1, 2, 3, 4, 5, 6, 8, 9, 10, 12<\/code> is the sequence of the first <code>10<\/code> ugly numbers.<br \/>\nNote that <code>1<\/code> is typically treated as an ugly number.<\/p>\n<h3>\u601d\u8def<\/h3>\n<p>\u300a\u5251\u6307Offer\u300b\u4e0a\u7684\u539f\u989834\uff0c\u6240\u4ee5\u5c31\u8bf4\u4e2a\u5927\u6982\u5427\u3002<br \/>\n\u4e0b\u4e00\u4e2a\u4e11\u6570\u662f\u4e4b\u524d\u7684\u4e11\u6570\uff08\u6700\u521d\u662f1\uff09\u4e58\u4ee52\u30013\u6216\u80055\u5f97\u5230\u7684\uff0c\u6240\u4ee5\u4e0b\u4e00\u4e2a\u4e11\u6570\u5c31\u662f\u4e4b\u524d\u7684\u67d0\u4e2a\u6570\u4e58\u51fa\u6765\u7684\u3002\u8fd9\u6837\u7684\u627e\u6cd5\u6bd4\u4ece1\u5230n\u4e00\u4e2a\u4e2a\u5224\u65ad\u662f\u4e0d\u662f\u4e11\u6570\u9ad8\u6548\u5f88\u591a\uff0c\u4e0d\u7136\u6bcf\u4e2a\u6570\u90fd\u8981\u53bb\u9664\u4e2a2\u30013\u30015\u5224\u65ad\u4e00\u4e0b\u3002<br \/>\n\u7531\u4e8e\u8981\u7ba1\u6b21\u5e8f\u95ee\u9898\uff0c\u6240\u4ee5\u5b89\u6392\u4e09\u4e2a\u6307\u9488\uff0c\u5206\u522b\u8bb0\u5f55\u4e58\u4ee52\u30013\u30015\u540e\u4e0d\u8d85\u8fc7\u5f53\u524d\u6700\u5927\u4e11\u6570\u7684\u4f4d\u7f6e\uff0c\u5047\u8bbe\u662fp2, p3, p5\uff0c\u4e0b\u4e00\u6b21\u627e\u4e0b\u4e2a\u4e11\u6570\u7684\u65f6\u5019\uff0c\u4ece(<em>p2)<\/em>2\u3001(<em>p3)<\/em>3\u3001(<em>p5)<\/em>5\u91cc\u5934\u627e\u5230\u4e2a\u6700\u5c0f\u7684\uff0c\u52a0\u5728\u6570\u7ec4\u6700\u540e\u9762\uff0c\u7136\u540e\u66f4\u65b0\u4e09\u4e2a\u6307\u9488\u7684\u503c\uff0c\u5982\u6b64\u5f80\u590d\u2026\u2026<\/p>\n<h3>\u4ee3\u7801<\/h3>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    int nthUglyNumber(int n) {\n        if(n &lt;= 0)\n            return 0;\n        int* uglyAry = new int[n];\n        uglyAry[0] = 1;\n        int nextPos = 1;\n        int *pNextUgly2 = uglyAry;\n        int *pNextUgly3 = uglyAry;\n        int *pNextUgly5 = uglyAry;\n        while(nextPos &lt; n){\n            int nextUgly = min3(*pNextUgly2 * 2, *pNextUgly3 * 3, *pNextUgly5 * 5);\n            uglyAry[nextPos] = nextUgly;\n            \/\/Move forward to find next possible candidates\n            while(*pNextUgly2 * 2 &lt;= nextUgly)\n                pNextUgly2++;\n            while(*pNextUgly3 * 3 &lt;= nextUgly)\n                pNextUgly3++;\n            while(*pNextUgly5 * 5 &lt;= nextUgly)\n                pNextUgly5++;\n            nextPos++;\n        }\n        int ugly = uglyAry[n-1];\n        delete []uglyAry;\n        return ugly;\n    }\n    int min3(int n1, int n2, int n3){\n        int min = n1&lt;n2?n1:n2;\n        min = min&lt;n3?min:n3;\n        return min;\n    }\n};<\/pre>\n<p>&nbsp;<br \/>\n&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an ugly number. \u601d\u8def \u300a\u5251\u6307Offer\u300b\u4e0a\u7684\u539f\u989834\uff0c\u6240\u4ee5\u5c31\u8bf4\u4e2a\u5927\u6982\u5427\u3002 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1911","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1911","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1911"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1911\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1911"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1911"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}