解题思路

数列是 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 …… 规律是：1 出现 1 次，2 出现 2 次，3 出现 3 次…… 要问第 n 项是多少。

思路：

把数列看成一节一节的：

• 数字 1 占 1 个位置
• 数字 2 占 2 个位置
• 数字 3 占 3 个位置
• ……

用一个变量 s 记录已经占了多少个位置，i 表示当前是哪个数字：

1. s 从 0 开始，i 从 0 开始
2. 只要 s 还没到 n，就 i+1，然后 s 加上 i（因为数字 i 出现 i 次）
3. 当 s 超过或等于 n 时，当前的 i 就是第 n 项的值

举个例子 n=10：

• i=1，s=1（数字1占1位）
• i=2，s=3（数字2占2位，累计3位）
• i=3，s=6（累计6位）
• i=4，s=10（累计10位，达到第10位）
• 所以第 10 项是 4

参考代码

#include <iostream>
using namespace std;

int main() {
    int n, s = 0, i = 0;
    cin >> n;

    while (s < n) {
        i++;
        s += i;  // 数字 i 会出现 i 次
    }

    cout << i << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(√N)，约 1+2+...+i 接近 n，i 约根号 n
• 空间复杂度：O(1)