第 k 个数

Posted on In Views: Waline: Views: Symbols count in article: 535 Reading time ≈ 1 mins.

题解方法

  • 多路并归

多路并归

  • 后续数值均基于已有数值乘以 3、5 或 7 而来
  • 所有数值均可归为 $arr[idx] \times 系数（即3、5、7）$ 得来的三个序列，使用三个指针分别指向上述序列
  • 生成新的数值时，判断所属序列（不唯一），其对应指针右移

核心代码

多路并归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int[] cache = new int[k];
cache[0] = 1;
// 三序列指针
int idx3 = 0;
int idx5 = 0;
int idx7 = 0;

for (int i = 1; i < k; i++) {
    // 三序列最小值
    int num3 = cache[idx3] * 3;
    int num5 = cache[idx5] * 5;
    int num7 = cache[idx7] * 7;

    cache[i] = Math.min(Math.min(num3, num5), num7);
    // 三序列指针移动
    if (cache[i] == num3) {
        idx3++;
    }
    if (cache[i] == num5) {
        idx5++;
    }
    if (cache[i] == num7) {
        idx7++;
    }
}

题目来源

面试题 17.09. 第 k 个数 - 力扣（LeetCode）