Giả sử em có 1 Danh sách ghế có ID như dưới, giá trị bắt đầu là 1.
VD: có dãy ID 1-2-3-4-5-6-7 . Xóa ghế có ID thứ 4 , 5 => dãy ID mới 1-2-3-6-7
Bình thường nếu em thêm thì sẽ lấy ID cuối cùng cộng thêm 1, có nghĩa là ID mới sẽ là 8.
Nhưng thầy yêu cầu khi thêm mới thì phải thêm lại các ID đã xóa. Nếu duyệt và kiểm tra số liền trước bé hơn số liền sau 1 đơn vị thì cách làm này không tối ưu.
Mong mọi người giúp đỡ em hướng giải quyết khác ạ. Em cảm ơn!!
Hỏi về giải thuật tối ưu của bài xoá phần tử khỏi dãy
Thay vì xóa và quên các số đã xóa, hãy đẩy chúng vào mảng hoặc vector. Khi thêm thì lấy trong mảng/vector đó thêm vào.
2 Likes
Bạn có thể bỏ ID bị xóa đó vào 1 priority queue. Kiểm tra Queue trước khi thêm. Nếu Queue ko rỗng thì pop rồi add. Rỗng thì phần tử cuối cộng 1.
6 Likes
Dạ em cảm ơn nhiều ạ!
dùng 2 mảng:
m1 lưu danh sách id hiện tại
m2 mảng tạm, lưu toàn bộ các id được thêm vào
khi nào xóa id thì lấy m2 ngoại trừ id đã xóa ghi vào m1
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?