题目地址

https://leetcode-cn.com/problems/get-kth-magic-number-lcci/

题目描述

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9

题解

（一）最小堆

class Solution {
    public int getKthMagicNumber(int k) {
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.add(1L);

        Set<Long> used = new HashSet<>();
        long cur = 1;
        for (int i = 0; i < k; ++ i) {
            while (used.contains(cur)) {
                cur = minHeap.poll();
            }

            minHeap.add(cur * 3);
            minHeap.add(cur * 5);
            minHeap.add(cur * 7);

            used.add(cur);
        }
        return (int)cur;
    }
}

提示：用 Integer 会溢出，要用 Long 类型。

（二）三指针

class Solution {
    public int getKthMagicNumber(int k) {
        int arr[] = new int[k + 1];
        arr[0] = 1;
        int cur3 = 0;
        int cur5 = 0;
        int cur7 = 0;
        for (int i = 1; i < k; ++ i) {
            int min = Math.min(Math.min(arr[cur3] * 3, arr[cur5] * 5), arr[cur7] * 7);

            if (min == arr[cur3] * 3) cur3++;
            if (min == arr[cur5] * 5) cur5++;
            if (min == arr[cur7] * 7) cur7++;

            arr[i] = min;
        }
        return arr[k - 1];
    }
}

构造出来的 arr 数组时有序递增的。

参考

• https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/get-kth-magic-number-lcci