Dạng bài sắp xếp dựa trên trọng số sử dụng Heap

Bạn có thể rất dễ nhận ra dạng bài này khi thường đề sẽ yêu cầu bạn sắp xếp lại một mảng hay một chuỗi sao cho các ký tự liền nhau không giống nhau.

Ví dụ:

• Leetcode 767 - Reorganize String
• Leetcode 1054 - Distant Barcodes

Với dạng này thì thường cách làm sẽ như sau:

• Bạn sẽ đếm số lượng các phần tử trong chuỗi/mảng dưới dạng mảng Y có phần tử con x dạng [số lần xuất hiện giá trí một giá trị, giá trị đó]
• Sau đó bạn heapify mảng Y dưới dạng maxheap dựa trên số lượt xuất hiện của một giá trị hay x[0]
• Sau đó bạn
  • Pop từng phần tử x ở heap, trừ đi 1 lần xuất hiện vào x[1]
  • Thêm giá trị x[0] vào chuỗi/mảng mới
  • Thêm ngược lại bộ đếm x vào heap, điều này thể hiện bạn luôn ưu tiên phần tử nào còn thừa nhiều nhất để sắp xếp.

Chú ý: để heapify được mảng Y mà x có dạng trên, thì bạn phải đặt giá trị sẽ ưu tiên heapify ở phía trước, đó là lý do vì sao bạn thấy cách tổ chức là [số lần xuất hiện giá trí một giá trị, giá trị đó] mà không phải ngược lại.

Tất nhiên bạn vẫn phải biến thêm dấu âm vào x[0] thành [-số lần xuất hiện giá trí một giá trị, giá trị đó] để tạo được maxheap khi dùng heapq.heapify().

Chúc bạn làm bài tốt.