Đây là câu hỏi phỏng vấn. Bạn cần thiết kế một hàng đợi chứa các giá trị nguyên và có hàm getMedian() trả về phần tử trung bình của hàng đợi hiện tại. Bạn có thể sử dụng không gian thêm O (n).thiết kế một Hàng đợi hỗ trợ chức năng getMedian
Có thể getMedian() được thực hiện với độ phức tạp thời gian < O (n)?
Ví dụ: Khi hàng đợi có các giá trị sau (2, 1, 2, 2, 6, 4, 2, 5) phương thức này trả về 2 và không loại bỏ đối tượng đó.
Việc thực hiện được biết đến với vấn đề của bạn là như vậy:
Những gì bạn cần phải thực hiện là 2 đống, ai sẽ trở thành một min-heap và người kia là max-heap.
Ngoài ra, bạn sẽ cần số nguyên để cho chúng tôi biết số lượng đối tượng trong hàng đợi của bạn.
Các trở ngại cho đống như sau:
1. min-heap sẽ có các đối tượng lớn hơn của hàng đợi của bạn
2. max-heap sẽ có các đối tượng nhỏ hơn của hàng đợi của bạn
3. max-heap sẽ có cùng một hoặc 1 đối tượng khác so với min-heap của bạn
Bằng cách đó, nếu bạn có một số lẻ đối tượng thì trung bình sẽ chính xác là đối tượng tối đa trong vùng tối đa của bạn. Nếu bạn có số lượng đối tượng bằng nhau, thì trung bình của bạn sẽ là trung bình của cả hai gốc của vùng heaps (tối đa của heap tối đa, min của min-heap). Điều quan trọng là cần lưu ý rằng nếu đống của bạn trở nên không đồng đều, ví dụ nếu bạn sẽ "bật" từ một đống nhất định, bạn sẽ cần phải loại bỏ từ đống khác và di chuyển nó. Nhưng đó không phải là vấn đề vì tất cả những gì bạn cần để giải quyết là nguồn gốc của đống của bạn và không có gì hơn.
Sự phức tạp thời gian của getMedian trở thành O (1)
Chỉ cần tìm thấy một bài báo về đề tài này: link
trả lời bình luận
Các max-đống giữ nửa nhỏ các yếu tố.
Khi bạn thêm số mới vào hàng đợi, trước tiên bạn kiểm tra số lượng đối tượng trong hàng đợi là gì.
nếu số bạn đang thêm là số chẵn, điều đó có nghĩa là số cần được thêm vào vùng tối đa khi cả hai hàng có cùng kích thước.
Sau đó, bạn sẽ thấy giá trị tối đa trong vùng tối đa là gì.
Nếu số đó lớn hơn số ur, bạn chỉ có thể chèn nó vào vùng tối đa.
nếu nó nhỏ hơn, có nghĩa là số mới ur có thể lớn hơn số trong min-heap.
để bạn biết min trong min-heap là gì.
nếu số của bạn nhỏ hơn số phút tối thiểu, bạn có thể chèn số đó vào heap tối đa, nếu nó lớn hơn, sau đó u di chuyển phút trong min-heap đến vùng tối đa và chèn số mới của bạn vào min-heap.
Nếu số là một số lẻ, bạn cần phải thêm vào min-heap khi heap tối đa có thêm một số nữa, v.v ..
Đó là một chút phức tạp nhưng nếu bạn vẫn không hiểu tôi không nhớ psuedo mã hóa nó cho bạn
Nếu hàng đợi có phần tử n thì giá trị tối đa của heap tối đa lớn hơn ít nhất n/2 phần tử (tức là các phần tử trong vùng tối đa). Nhưng làm thế nào bạn có thể chắc chắn rằng min-heap không có bất kỳ phần tử nào nhỏ hơn max của heap tối đa, bởi vì nếu max của max-heap lớn hơn bất kỳ phần tử nào trong min-heap thì chúng ta có nhiều hơn số n/2 nhỏ hơn số tối đa của heap tối đa. Đúng nếu tôi đã sai lầm. – user913359
bị chỉnh sửa bài đăng của tôi vì tôi không thể viết tất cả bài viết đó dưới dạng nhận xét – Yarneo
@Yarneo: bài viết về hàng đợi * ưu tiên *, trong khi OP yêu cầu * hàng đợi *. Tôi biết bạn có thể thực hiện hàng đợi bằng hàng đợi ưu tiên bằng cách ưu tiên phần tử ih được thêm vào (hoặc -i, tùy thuộc vào mức độ ưu tiên của bạn), nhưng điều đó sẽ làm tăng tính toán trung bình của bạn nếu tôi hiểu nó phần tử có mức độ ưu tiên trung bình, tức là mục ở giữa hàng đợi ... –
Không phải là trung bình 2 giờ? –
Xin lỗi, tôi đã thay đổi ví dụ ngay bây giờ. – user913359
hàng đợi có số lượng đối tượng tối đa mà nó có thể chứa không? làm tất cả các chức năng khác của hàng đợi như push và pop cần phải ở trong cùng một sự phức tạp? – Yarneo