i164 - 比對卡片(進階版)
題目描述
題目描述了阿宏老師和學生進行比對卡片的遊戲。老師和學生各有 N 張卡片，老師希望學生找到自己卡片中與老師卡片數字相同且位置差距最小的卡片。如果找到，記錄位置差；否則，記錄 -1。
解題思路
這題的核心在於對於老師的每一張卡片，在學生的卡片中找到最接近的相同數字。為了提高效率，我們可以使用 vector 儲存每個數字在學生卡片中的所有索引。然後，對於老師的每一張卡片，我們在對應的 vector 中使用二分搜尋找到最接近的索引。具體來說，對於老師的第 i 張卡片，我們在學生卡片中找到數字 a[i] 的所有索引，然後找到距離 i 最近的索引。如果找不到相同的數字，則輸出 -1。
複雜度分析
- 時間複雜度: O(N log N)
- 遍歷老師的卡片需要 O(N) 時間。
- 對於每張老師的卡片，在學生的
vector中進行二分搜尋需要 O(log N) 時間。 - 因此，總時間複雜度為 O(N log N)。
- 空間複雜度: O(N)
- 使用
vector儲存每個數字在學生卡片中的索引，最壞情況下，每個數字都只出現一次，因此需要 O(N) 空間。
- 使用
程式碼
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,a[100005],x;
vector <int> v[100005];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
}
for(int i=0;i<n;++i){
cin >> x;
v[x].push_back(i);
}
for(int i=0;i<n;++i){
if(v[a[i]].size()==0){
cout << "-1 ";
//cout << "-1\n";
}
else{
int it1=lower_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin(),it2=0;
if(it1>0)it2=it1-1;
if(it1==v[a[i]].size())it1-=1;
it1=v[a[i]][it1];
it2=v[a[i]][it2];
//cout << i << " " << it1 << " " << it2 << "\n";
cout << min(abs(i-it1),abs(i-it2)) << " ";
}
}
}