题解 | 疯狂序列
疯狂序列
https://www.nowcoder.com/practice/dd8f34e9b83e412bab0b45a845889d34
解题思路
我们需要找到一个无限长的数字序列，其中数字k在该序列中正好出现k次。序列的前几项如下：
- 1
- 2, 2
- 3, 3, 3
- 4, 4, 4, 4
- 5, 5, 5, 5, 5
- ...
可以观察到，数字k的最后一个出现位置是1 + 2 + 3 + ... + k = k * (k + 1) / 2。因此，我们可以通过求和公式来确定n项所在的数字。
算法步骤：
- 确定数字k：通过不断累加
k，直到k * (k + 1) / 2大于或等于n。 - 输出结果：当找到合适的
k后，k就是数字序列的第n项。
代码
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long k = 1;
long long total = 0;
while (total < n) {
total += k;
k++;
}
cout << k - 1 << endl; // k-1是我们需要的数字
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long k = 1;
long total = 0;
while (total < n) {
total += k;
k++;
}
System.out.println(k - 1); // k-1是我们需要的数字
sc.close();
}
}
def find_nth_term(n):
k = 1
total = 0
while total < n:
total += k
k += 1
return k - 1 # k-1是我们需要的数字
# 测试代码
if __name__ == "__main__":
n = int(input())
result = find_nth_term(n)
print(result) # 输出第n项
算法及复杂度
- 算法：通过累加求和确定数字
- 时间复杂度：
，因为总和公式是二次的
- 空间复杂度：
，只使用常数额外空间
叫他简历发过来
