c669 - missing and duplicate
題目描述
題目給定 T 個打亂的等差數列，要求找出數列中缺失的數字 (m) 以及重複的數字 (d)。數列長度至少為 5，缺失數字 m 介於數列的最大值和最小值之間，重複數字 d 介於數列的最大值和最小值之間。
解題思路
程式碼首先讀取測試案例數量 T。對於每個測試案例，程式碼讀取一個字串，然後將其解析為整數數列。它使用一個迴圈遍歷數列，計算數列中所有數字的總和 (total)，並使用一個布林變數 f 和一個整數陣列 fd 來追蹤重複的數字 d。同時，程式碼也記錄數列的最大值 (ma) 和最小值 (mi)。
在迴圈結束後，程式碼使用等差數列的求和公式計算數列的預期總和 (sum)，然後使用公式 sum - total + d 計算缺失的數字 m。最後，程式碼輸出 m 和 d。
程式碼的核心思想是利用等差數列的特性，通過計算實際總和和預期總和之間的差來找到缺失的數字。重複數字的查找則是在遍歷數列的過程中完成的。
複雜度分析
- 時間複雜度: O(N)，其中 N 是數列的長度。程式碼需要遍歷數列一次來計算總和、查找重複數字以及計算最大值和最小值。
- 空間複雜度: O(1)。程式碼使用的額外空間是常數級別的，例如 fd 陣列的大小是固定的 (1001)，與輸入數列的長度無關。
程式碼
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
string a;
getline(cin,a);
while(t--){
getline(cin,a);
a+=' ';
int al=a.length(),d=0,total=0,tmp=0,fd[1001]={0},it=0,mi=99999999,ma=-99999999;
bool f=0;
for(int i=0;i<al;++i){
if(a[i]==' '){
total+=tmp;
if(f==0){
for(int j=0;j<it;++j){
if(fd[j]==tmp){
f=1;
d=tmp;
break;
}
}
fd[it]=tmp;
}
++it;
ma=max(ma,tmp);
mi=min(mi,tmp);
tmp=0;
}
else{
tmp*=10;
tmp+=a[i]-48;
}
}
int sum=(ma+mi)*it/2;
cout << sum-total+d << " " << d << "\n";
}
}