e529 - 00482 - Permutation Arrays

🔗 前往 ZeroJudge 原題

題目描述

題目要求根據給定的索引陣列 p 對數據陣列 x 進行置換，並輸出置換後的陣列 x。索引陣列 p 包含從 1 到 n 的數字，表示數據陣列 x 中元素的新位置。

解題思路

程式碼首先讀取測試案例的數量 t。對於每個測試案例，程式碼讀取索引陣列 a 和數據陣列 ans。索引陣列 a 的元素表示數據陣列 ans 中元素的新位置。程式碼使用索引陣列 a 將數據陣列 ans 中的元素重新排列，然後輸出置換後的數據陣列 ans。程式碼使用 getchar() 讀取換行符，以正確解析輸入。

複雜度分析

• 時間複雜度: O(n)，其中 n 是陣列的大小。程式碼需要遍歷索引陣列和數據陣列一次。
• 空間複雜度: O(n)，程式碼使用一個大小為 1001 的陣列 ans 儲存數據陣列。

程式碼

#include <iostream>
using namespace std;
string ans[1001];
int main(){
	int t;
	cin >> t;
	string v;
	char c;
	while(t--){
		int a[1001]={0},it=0;
		while(cin >> a[it]){
			++it;
			c=getchar();
			if(c=='\n')break;
		}
		for(int i=0;i<it;++i){
			cin >> v;
			ans[a[i]-1]=v;
		}
		for(int i=0;i<it;++i)
			cout << ans[i] << "\n";
		if(t)cout << "\n"; 
	}
}