Mô tả: Cho một mảng score có độ dài n. Trong đó, score[i] đại diện cho điểm số của người chơi thứ i trong một cuộc thi. Tất cả các điểm số đều khác nhau.
Yêu cầu: Tìm ra xếp hạng tương đối của từng người chơi và trao giải cho ba người đứng đầu. Ba người đứng đầu sẽ được trao lần lượt “Huy chương vàng” ("Gold Medal"), “Huy chương bạc” ("Silver Medal") và “Huy chương đồng” ("Bronze Medal").
Chú ý:
n==score.length.
1≤n≤104.
0≤score[i]≤106.
Tất cả các giá trị trong mảng score đều khác nhau.
Ví dụ:
Ví dụ 1:
Ví dụ 2:
Ý tưởng giải quyết
Ý tưởng 1: Sắp xếp
Sắp xếp mảng score theo thứ tự tăng dần.
Thay thế ba phần tử ở vị trí đầu tiên bằng các chuỗi tương ứng: "Gold Medal", "Silver Medal", "Bronze Medal".
Ý tưởng 1: Mã giả
Ý tưởng 1: Phân tích độ phức tạp
Độ phức tạp thời gian: O(n×logn). Vì sử dụng thuật toán sắp xếp Shell với độ phức tạp thời gian là O(n×logn).