Hướng dẫn thuật toán

Link đề bài

Chủ đề: Tìm tần suất lớn nhất (Max Frequency)

1. Phân tích bằng ngôn ngữ tự nhiên

Mục tiêu của bài toán là tìm một nhóm học sinh có chiều cao bằng nhau, sao cho số lượng học sinh trong nhóm đó là lớn nhất. Nếu có nhiều nhóm có số lượng bằng nhau, ta chọn nhóm có chiều cao lớn nhất.

• Vấn đề: Số lượng học sinh () có thể lên đến , và chiều cao () có thể lên đến . Ta không thể dùng một mảng (array) đơn giản để đếm tần suất vì chiều cao quá lớn.
• Giải pháp (Sử dụng Sắp xếp):
  1. Sắp xếp: Sắp xếp toàn bộ danh sách chiều cao . Sau khi sắp xếp, các học sinh có chiều cao bằng nhau sẽ đứng cạnh nhau, tạo thành các nhóm liên tiếp.
  2. Duyệt và Đếm: Duyệt qua danh sách đã sắp xếp. Mỗi khi gặp một chiều cao mới, ta bắt đầu đếm số lượng các phần tử bằng nó. Đây chính là tần suất (số lượng) của nhóm đó.
  3. Cập nhật Kết quả: Trong quá trình đếm, ta liên tục so sánh số lượng hiện tại với số lượng lớn nhất đã tìm thấy (max_count).
     • Nếu số lượng hiện tại > max_count, ta cập nhật cả max_count và chiều cao tương ứng.
     • Nếu số lượng hiện tại = max_count: Vì mảng đã được sắp xếp, chiều cao hiện tại chắc chắn lớn hơn chiều cao đã lưu trước đó. Do yêu cầu chọn chiều cao lớn hơn khi có hòa về số lượng, ta cập nhật chiều cao mới.

2. Biểu diễn thuật toán (Pseudo-code)

H = Danh sách chiều cao đầu vào
N = Kích thước danh sách H

1. Sắp xếp H theo thứ tự tăng dần.

2. Khởi tạo:
   max_count = 0 
   max_height = 0 
   
3. Bắt đầu duyệt (sử dụng chỉ số i làm điểm bắt đầu của một nhóm):
   i = 0
   trong khi i < N:
       current_height = H[i]
       current_count = 1
       
       // Bước 3.1: Đếm số lượng phần tử bằng current_height (trong nhóm liên tiếp)
       j = i + 1
       trong khi j < N VÀ H[j] == current_height:
           current_count = current_count + 1
           j = j + 1
           
       // Bước 3.2: So sánh và Cập nhật kết quả
       NẾU current_count > max_count:
           max_count = current_count
           max_height = current_height
       NGƯỢC LẠI NẾU current_count == max_count:
           // Trường hợp hòa: Chọn chiều cao lớn hơn.
           // Vì mảng đã sắp xếp, current_height luôn lớn hơn chiều cao trước đó.
           max_height = current_height
       
       // Bước 3.3: Di chuyển i đến đầu nhóm tiếp theo
       i = j 

4. In ra max_height và max_count