面试题 17.09

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. Note that 3, 5, and 7 do not have to be factors, but it should not have any other prime factors. For example, the first several multiples would be (in order) 1, 3, 5, 7, 9, 15, 21.

Example 1:

Input: k = 5

Output: 9

Solutions

• The same as problem 264 Ugly number II.

• treeset

class Solution {
public:
    int getKthMagicNumber(int k) {
        set<size_t> s {1};
        for (int i = 1; i < k; i++) {
            auto min = *s.begin();
            s.erase(s.begin());
            s.insert({min * 3, min * 5, min * 7});
        }
        return *s.begin();
    }
};

1. dynamic programming or merge sorted lists

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> dp(k + 1, 1);
        int i3 = 0, i5 = 0, i7 = 0;
        for (int i = 1; i < k; i++) {
            int minval = min(dp[i3] * 3, min(dp[i5] * 5, dp[i7] * 7));
            if (minval == dp[i3] * 3)
                i3++;
            if (minval == dp[i5] * 5)
                i5++;
            if (minval == dp[i7] * 7)
                i7++;
            dp[i] = minval;
        }

        return dp[k - 1];
    }
};