面试题17.09.第k个数

链接：面试题17.09.第k个数
难度：Medium
标签：哈希表、数学、动态规划、堆（优先队列）
简介：有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

题解 1 - typescript

• 编辑时间：2021-03-14
• 执行用时：92ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：依次获取最小值排序。

function getKthMagicNumber(k: number): number {
  if (k === 1) return 1;
  let p3 = 0,
    p5 = 0,
    p7 = 0;
  const arr: number[] = [1];
  while (arr.length <= k) {
    const num3 = arr[p3] * 3,
      num5 = arr[p5] * 5,
      num7 = arr[p7] * 7;
    if (num3 < num5 && num3 < num7) {
      while (true) {
        const nextNum = arr[++p3] * 3;
        if (nextNum !== num5 && nextNum !== num7) break;
      }
      arr.push(num3);
    }
    if (num5 < num3 && num5 < num7) {
      while (true) {
        const nextNum = arr[++p5] * 5;
        if (nextNum !== num3 && nextNum !== num7) break;
      }
      arr.push(num5);
    }
    if (num7 < num5 && num7 < num3) {
      while (true) {
        const nextNum = arr[++p7] * 7;
        if (nextNum !== num5 && nextNum !== num3) break;
      }
      arr.push(num7);
    }
  }
  return arr[k - 1];
}

题解 2 - typescript

• 编辑时间：2021-03-14
• 执行用时：108ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function getKthMagicNumber(k: number): number {
  if (k === 1) return 1;
  let p3 = 0,
    p5 = 0,
    p7 = 0;
  const arr: number[] = [1];
  while (arr.length < k) {
    const num3 = arr[p3] * 3,
      num5 = arr[p5] * 5,
      num7 = arr[p7] * 7;
    const num = Math.min(num3, num5, num7);
    if (num === num3) p3++;
    if (num === num5) p5++;
    if (num === num7) p7++;
    arr.push(num);
  }
  return arr[k - 1];
}

题解 3 - cpp

• 编辑时间：2022-09-28
• 内存消耗：6.1MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> list(k);
        list[0] = 1;
        int p[3] = {0};
        for (int i = 1; i < k; i++) {
            int next = min(list[p[0]] * 3, min(list[p[1]] * 5, list[p[2]] * 7));
            list[i] = next;
            if (next % 3 == 0) p[0]++;
            if (next % 5 == 0) p[1]++;
            if (next % 7 == 0) p[2]++;
        }
        return list.back();
    }
};