题解 | #序列找数#
序列找数
https://www.nowcoder.com/practice/a7d1856a72404ea69fdfb5786d65539c
解题思路
- 这是一个查找缺失数字的问题，可以使用求和的方法解决
- 解题步骤：
- 计算从
到
的所有数字之和
- 计算给定序列中所有数字之和
- 两个和的差值就是缺失的数字
- 计算从
- 这种方法避免了排序，时间复杂度为
代码
#include <iostream>
using namespace std;
int main() {
int n, sum = 0, sum1 = 0;
cin >> n;
// 计算0到n的和
for(int i = 0; i <= n; i++) {
sum += i;
}
// 计算给定序列的和
for(int i = 0; i < n; i++) {
int temp;
cin >> temp;
sum1 += temp;
}
// 输出差值
cout << sum - sum1 << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0, sum1 = 0;
// 计算0到n的和
for(int i = 0; i <= n; i++) {
sum += i;
}
// 计算给定序列的和
for(int i = 0; i < n; i++) {
sum1 += sc.nextInt();
}
// 输出差值
System.out.println(sum - sum1);
}
}
nums = list(map(int, input().split()))
n = nums[0]
sum_total = sum(range(n + 1))
nums = nums[1:]
sum_given = sum(nums)
# 输出差值
print(sum_total - sum_given)
算法及复杂度
- 算法：数学求和
- 时间复杂度：
- 需要遍历一次序列
- 空间复杂度：
- 只需要常数额外空间
投递海尔等公司10个岗位