Sắp xếp số trong xâu (TS10 LQĐ, Đà Nẵng 2016)
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho một xâu \(S\) có chứa các kí tự số. Hãy sắp xếp các ký tự số trong \(S\) theo thứ tự không giảm nhưng giữ nguyên vị trí ban đầu của các kí tự khác (nếu có) trong xâu.
Input
- Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (\(|S| \leq 255\)).
Output
- In ra màn hình xâu đã được sắp xếp theo yêu cầu trên.
Example
Test 1
Input
744 Output
447Test 2
Input
Acb27h1h92gg Output
Acb12h2h79gg
Bình luận
Spoiler Alert
Do bài này tách các kí tự trong mảng nên các số nằm trong đoạn [0,9] vì vậy ta có thể dùng đếm phân phối cho tốc độ tối ưu nhất.
Sau khi bỏ vào danh sách đếm phân phối. Ta tạo 1 mảng để lưu lại các vị trí.
VD: Biểu diễn dưới dạng a[i] trong đó a là giá trị, i là tần số xuất hiện.
2[3] 4[0] 5[2]
-> 2 2 2 5 5
Sau đó thay thế các giá trị trong mảng cho các số trong chuỗi lần lượt từ trái qua phải.
Bài này giới hạn nhỏ thì dùng Bubble sort cho dễ (Complexity: \(O(|S|^2)\) time)
Mn cho hỏi, bài này chạy test cuối run sai mà sao chạy trong dev lại đúng???
bài này tách ra rồi sort
failed initializing là sao vậy sao em bị miết :_(