题目大意:让你找到第n个丑数。
Problem:
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, and n does not exceed 1690.
Solution:
C++ / O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: huahua // Running time: 6 ms class Solution { public: int nthUglyNumber(int n) { static vector<int> nums{1}; static int i2 = 0; static int i3 = 0; static int i5 = 0; while (nums.size() < n) { const int next2 = nums[i2] * 2; const int next3 = nums[i3] * 3; const int next5 = nums[i5] * 5; const int next = min(next2, min(next3, next5)); if (next == next2) ++i2; if (next == next3) ++i3; if (next == next5) ++i5; nums.push_back(next); } return nums[n - 1]; } }; |
C++ /query * O(NlogN)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 89 ms class Solution { public: int nthUglyNumber(int n) { vector<int> nums; for (long a = 1; a <= INT_MAX; a *= 2) for (long b = a; b <= INT_MAX; b *= 3) for (long c = b; c <= INT_MAX; c *= 5) nums.push_back(c); std::sort(nums.begin(), nums.end()); return nums[n - 1]; } }; |
C++ / static variables O(NlogN) + query*O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 7 ms class Solution { public: int nthUglyNumber(int n) { static vector<int> nums; if (nums.empty()) { for (long a = 1; a <= INT_MAX; a *= 2) for (long b = a; b <= INT_MAX; b *= 3) for (long c = b; c <= INT_MAX; c *= 5) nums.push_back(c); std::sort(nums.begin(), nums.end()); } return nums[n - 1]; } }; |
C++ / table O(1)
leetcode_264_table.cc
Related Problems:
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment