e340 - 差分練習

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個陣列 B，要求輸出其差分陣列 A。差分陣列的定義是 A[i] = B[i] - B[i-1] (當 i > 0)，A[0] = B[0]。 換句話說，題目要求計算相鄰元素之間的差值。

解題思路

這題的核心概念是差分陣列。我們可以迭代輸入的陣列 B，並計算每個元素與前一個元素的差值。第一個元素直接輸出即可。使用一個變數 b 儲存前一個元素的值，在迴圈中計算當前元素與 b 的差值，並將 b 更新為當前元素。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入陣列的大小。因為我們需要遍歷陣列一次。
• 空間複雜度: O(1)，因為我們只使用了幾個常數大小的變數。

程式碼

#include <stdio.h>
int main(){
	int b=0,c;
	scanf("%d",&c);
	while(scanf("%d",&c)!=EOF){
		printf("%d ",c-b);
		b=c;
	}
}