AC Python solution O(n) time O(n) space
def nthUglyNumber(self, n):\n        ugly = [1] * n\n        i2 = i3 = i5 = -1\n        x = v2 = v3 = v5 = 1\n        for k in xrange(n):\n            x = min(v
    def nthUglyNumber(self, n):\n        ugly = [1] * n\n        i2 = i3 = i5 = -1\n        x = v2 = v3 = v5 = 1\n        for k in xrange(n):\n            x = min(v2, v3, v5)\n            ugly[k] = x\n            if x == v2:\n                i2 += 1\n                v2 = ugly[i2] * 2\n            if x == v3:\n                i3 += 1\n                v3 = ugly[i3] * 3\n            if x == v5:\n                i5 += 1\n                v5 = ugly[i5] * 5\n        return x\n\n    # 596 / 596 test cases passed.\n    # Status: Accepted\n    # Runtime: 176 ms\n    # 94.23%\n\n\nThe keys are the same as hint under the problem. One thing is we do not compute the multiplication in the min instead we update the v if needed. Another thing is we can preallocate a size n list instead of append to the list n times in the loop.\n\nOf course we can use another loop to make it shorter. But it is also slower.\n\n    def nthUglyNumber(self, n):\n        ugly = [1] * n\n        primes = [2, 3, 5]\n        i = [-1] * 3\n        v = [1] * 3\n        for k in xrange(n):\n            ugly[k] = min(v)\n            for j in xrange(3):\n                if v[j] == ugly[k]:\n                    i[j] += 1\n                    v[j] = ugly[i[j]] * primes[j]\n        return ugly[-1]\n\n\n    # 596 / 596 test cases passed.\n    # Status: Accepted\n    # Runtime: 332 ms\n    # 29.89%
['Python']