e968 - 班級名單 (Student list)

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出一個班級中缺席的學生編號。輸入首先是一個整數 a，代表班級的學生總數。接下來，輸入一系列整數，代表出席學生的編號。輸出從 a 到 1 的整數，但只輸出那些沒有在出席名單中出現的編號。

解題思路

這題的解題思路是使用一個布林陣列來記錄每個學生是否出席。陣列的索引代表學生的編號，陣列的值為 1 表示學生出席，為 0 表示學生缺席。首先，初始化陣列的所有元素為 0。然後，讀取出席學生的編號，將對應陣列元素的值設為 1。最後，從 a 到 1 遍歷陣列，輸出所有值為 0 的索引。

複雜度分析

• 時間複雜度: O(n + m)，其中 n 是班級的學生總數，m 是出席學生的數量。
• 空間複雜度: O(n)，因為需要一個大小為 n 的布林陣列。

程式碼

#include <stdio.h>
int n[21];
int main(){
	int a,b;
	scanf("%d",&a);
	while(scanf("%d",&b)>0)
		n[b]=1;
	for(int i=a;i>0;i--)
		if(n[i]==0)
			printf("No. %d\n",i);
}