解题思路

  1. 这是一个查找缺失数字的问题,可以使用求和的方法解决
  2. 解题步骤:
    • 计算从 的所有数字之和
    • 计算给定序列中所有数字之和
    • 两个和的差值就是缺失的数字
  3. 这种方法避免了排序,时间复杂度为

代码

#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)

算法及复杂度

  • 算法:数学求和
  • 时间复杂度: - 需要遍历一次序列
  • 空间复杂度: - 只需要常数额外空间