k399 - 取貨 (Pickup)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個字串 s，包含若干不重複的字元。要求輸出每個字元在字串中出現的順序的排名。排名從 1 開始，相同順序的字元排名相同。

解題思路

這題的核心思想是利用 Hash Table (陣列) 記錄每個字元第一次出現的位置，然後對這些位置進行排序。排序後，每個字元的位置在排序後的陣列中的索引加 1 就是該字元的排名。

1. 建立一個大小為 256 的整數陣列 ans 作為 Hash Table，用於儲存每個字元第一次出現的位置。
2. 遍歷輸入字串 s，對於每個字元 s[i]，將其第一次出現的位置記錄在 ans[s[i]] 中，即 ans[s[i]] = i + 1。
3. 建立一個向量 a，用於儲存所有出現過的字元的排名。
4. 遍歷 ans 陣列，如果 ans[i] 不為 0，則將其加入向量 a。
5. 對向量 a 進行排序。
6. 再次遍歷輸入字串 s，對於每個字元 s[i]，在排序後的向量 a 中找到其排名，並輸出排名。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是字串的長度。主要時間花費在排序向量 a 上。遍歷字串和 Hash Table 的操作時間複雜度為 O(n)。
• 空間複雜度: O(1)，因為 ans 陣列的大小是固定的 (256)，a 向量的大小最多為 256。

程式碼

#include <bits/stdc++.h>
using namespace std;
int ans[256];
vector <int> a;
string s;
int main(){
	cin >> s;
	for(int i=0;i<s.size();++i){
		ans[s[i]]=i+1;
	}
	for(int i=0;i<256;++i){
		if(ans[i])a.push_back(ans[i]);
	}
	sort(a.begin(),a.end());
	for(int i=0;i<256;++i){
		if(ans[i]){
			cout << find(a.begin(),a.end(),ans[i])-a.begin()+1;
		}
	}
}