调皮的依依

[题目链接](https://www.nowcoder.com/practice/40ebefcc3dfa42cbb482ec1ef1a38b0e)

思路

老师在黑板上写了 $1, 2, \ldots, n$ 这个升序序列，依依声称自己只擦掉了一个数字。我们要判断他说的是不是真的。

什么情况下依依的说法可信？需要同时满足三个条件：

剩余个数对得上：黑板上剩 $m$ 个数，必须有 $m = n - 1$ ，少了不止一个或一个没少都不行。
保持严格升序：剩下的数必须是严格递增的，因为原来的序列就是升序排列的，擦掉一个数不会破坏其余数的相对顺序。
范围合法：每个数都在 $[1, n]$ 之内。

三个条件全满足的话，被擦掉的那个数就是总和之差： $1 + 2 + \cdots + n$ 减去黑板上剩余数字之和，即 $\frac{n(n+1)}{2} - \sum a_i$ 。

简单验证一下示例： $n = 4$ ，黑板上是 $1, 2, 3$ ，总和 $10 - 6 = 4$ ，输出 Yes 和 4。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for(int i = 0; i < m; i++) cin >> a[i];

    if(m != n - 1){
        cout << "No" << endl;
        return 0;
    }

    bool ok = true;
    for(int i = 0; i < m; i++){
        if(a[i] < 1 || a[i] > n) ok = false;
        if(i > 0 && a[i] <= a[i-1]) ok = false;
    }

    if(!ok){
        cout << "No" << endl;
        return 0;
    }

    long long total = (long long)n * (n + 1) / 2;
    long long sum = 0;
    for(int i = 0; i < m; i++) sum += a[i];
    long long missing = total - sum;

    if(missing < 1 || missing > n){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        cout << missing << 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 m = sc.nextInt();
        int[] a = new int[m];
        for (int i = 0; i < m; i++) a[i] = sc.nextInt();

        if (m != n - 1) {
            System.out.println("No");
            return;
        }

        boolean ok = true;
        for (int i = 0; i < m; i++) {
            if (a[i] < 1 || a[i] > n) ok = false;
            if (i > 0 && a[i] <= a[i - 1]) ok = false;
        }

        if (!ok) {
            System.out.println("No");
            return;
        }

        long total = (long) n * (n + 1) / 2;
        long sum = 0;
        for (int i = 0; i < m; i++) sum += a[i];
        long missing = total - sum;

        if (missing < 1 || missing > n) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
            System.out.println(missing);
        }
    }
}

n = int(input())
m = int(input())
a = list(map(int, input().split()))

if m != n - 1:
    print("No")
else:
    ok = True
    for i in range(m):
        if a[i] < 1 or a[i] > n:
            ok = False
        if i > 0 and a[i] <= a[i - 1]:
            ok = False
    if not ok:
        print("No")
    else:
        total = n * (n + 1) // 2
        missing = total - sum(a)
        if missing < 1 or missing > n:
            print("No")
        else:
            print("Yes")
            print(missing)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const m = parseInt(lines[1]);
    const a = lines[2].split(' ').map(Number);

    if (m !== n - 1) {
        console.log("No");
        return;
    }

    let ok = true;
    for (let i = 0; i < m; i++) {
        if (a[i] < 1 || a[i] > n) ok = false;
        if (i > 0 && a[i] <= a[i - 1]) ok = false;
    }

    if (!ok) {
        console.log("No");
        return;
    }

    let total = n * (n + 1) / 2;
    let s = 0;
    for (let i = 0; i < m; i++) s += a[i];
    let missing = total - s;

    if (missing < 1 || missing > n) {
        console.log("No");
    } else {
        console.log("Yes");
        console.log(missing);
    }
});

复杂度分析

时间复杂度： $O(m)$ ，遍历一次数组检查合法性并求和。
空间复杂度： $O(m)$ ，存储输入数组。