题目

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

思考

• 这是丑数题
• 定义3个指针a3,a5,a7, a3指向的数字永远乘以3， a5指向的数字永远乘以5， a7指向的数字永远乘以7
• 初始化所有指针都指向第一个丑数，即1
• 从s[a3]*3, a[a5]*5, s[a7]*7选取最小的一个数字作为丑数

代码

int min(int a3, int a5, int a7)
{
    int min = INT_MAX;
    a3 < min ? min = a3 : min;
    a5 < min ? min = a5 : min;
    a7 < min ? min = a7 : min;
    return min;
}
int getKthMagicNumber(int k) {
    if (k == 1)
        return 1;
    int* s = (int*)calloc(k, sizeof(int));
    s[0] = 1;
    int a3, a5, a7;
    a3 = a5 = a7 = 0;
    for (int i = 1; i < k; i++)
    {
        int temp = min(s[a3] * 3, s[a5] * 5, s[a7] * 7);
        if (s[a3] * 3 == temp)
            a3++;
        if (s[a5] * 5 == temp)
            a5++;
        if (s[a7] * 7 == temp)
            a7++;
        s[i] = temp;
    }
    return s[k - 1];
}