Ordered danh sách với O (1) truy cập ngẫu nhiên và loại bỏ

Question

Liệu có tồn tại một cấu trúc dữ liệu với các thuộc tính sau:

• Elements được lưu trữ trong một số thứ tự
• Truy cập vào phần tử tại một chỉ số cho mất O (1) thời gian (có thể được phân bổ)
• Xóa một phần tử mất giá trị O (1) và thay đổi chỉ số một cách thích hợp (vì vậy nếu phần tử 0 bị xóa, truy cập tiếp theo đến phần tử 0 sẽ trả về phần tử cũ 1)

Đối với ngữ cảnh, tôi đã giảm câu hỏi thuật toán từ một cuộc thi lập trình thành:

Hơn m truy vấn, trả về số tích cực nhỏ nhất chưa được trả lại. Bạn có thể giả định số được trả về ít hơn một số hằng số n.

Nếu cấu trúc dữ liệu ở trên tồn tại, thì bạn có thể thực hiện việc này trong thời gian O(m), bằng cách tạo danh sách các số từ 1 đến n. Sau đó, đối với mỗi truy vấn, tìm phần tử tại chỉ mục k và xóa phần tử đó. Trong suốt cuộc thi, giải pháp của tôi đã kết thúc là O(m^2) trên một số đầu vào nhất định.

Tôi khá chắc chắn rằng bạn có thể thực hiện việc này trong O(m log m) với cây tìm kiếm nhị phân, nhưng tôi tự hỏi nếu lý tưởng O(m) có thể truy cập được. Nội dung tôi tìm thấy trực tuyến có xu hướng gần gũi, nhưng không hoàn toàn ở đó - phần phức tạp là các yếu tố bạn xóa có thể từ bất kỳ đâu trong danh sách.

Answer 1

1. cũng loại bỏ O(1) có thể với linked list

   mỗi phần tử có con trỏ tới phần tử tiếp theo và trước đó để loại bỏ chỉ xóa phần tử và đặt con trỏ của các nước láng giềng như:

   element[ix-1].next=element[ix+1].prev 
   

2. truy cập các phần tử đã đặt hàng tại chỉ mục trong O(1) có thể được thực hiện với indexed arrays

   vì vậy bạn phải mảng có thứ tự như dat[] và mảng chỉ số như idx[] truy cập của nguyên tố ix chỉ là:

   dat[idx[ix]] 
   

3. Bây giờ vấn đề là phải có các đặc tính này cùng một lúc

   bạn có thể cố gắng để có danh sách liên kết với mảng chỉ mục nhưng việc loại bỏ cần cập nhật bảng chỉ mục là O(N) trong trường hợp xấu nhất.

   nếu bạn chỉ có chỉ số mảng sau đó loại bỏ cũng là O(N)

   nếu bạn có chỉ số trong một số hình thức của một cấu trúc cây thì việc loại bỏ có thể được gần gũi với O(log(N)) nhưng việc tiếp cận cũng sẽ vào khoảng O(log(N))

Answer 2

Tôi tin rằng có cấu trúc sẽ thực hiện cả hai điều này trong thời gian O (n), trong đó n là số điểm đã bị xóa và không phải là tổng kích thước. Vì vậy, nếu số bạn đang xóa nhỏ hơn kích thước của mảng, nó gần với O (1).

Về cơ bản, tất cả dữ liệu được lưu trữ trong một mảng. Ngoài ra còn có hàng đợi ưu tiên cho các phần tử đã xóa. Khởi như vậy:

Data = [0, 1, 2, ..., m] 
removed = new list 

Sau đó, để loại bỏ một phần tử, bạn thêm đó là chỉ số ban đầu (xem dưới đây để biết làm thế nào để có được điều này) vào hàng đợi ưu tiên (được sắp xếp theo kích thước của phần tử với nhỏ ở phía trước) và để nguyên mảng đó. Vì vậy, loại bỏ các yếu tố thứ 3:

Data = [0, 1, 2, 3,..., m] 
removed = 2 

Sau đó, những gì bây giờ là lần thứ 4 và được thứ 5:

Data = [0, 1, 2, 3,..., m] 
removed = 2 -> 4 

Sau đó, những gì bây giờ là lần thứ 3 và là lần thứ 4:

Data = [0, 1, 2, 3,..., m] 
removed = 2 -> 3 -> 4 

Hiện hành truy cập một phần tử, bạn bắt đầu với chỉ mục của nó. Sau đó, bạn lặp lại dọc theo danh sách đã xóa, mỗi lần tăng chỉ mục, cho đến khi bạn đạt đến một phần tử lớn hơn giá trị tăng của chỉ mục. Điều này sẽ cung cấp cho bạn chỉ mục gốc (ví dụ: vị trí trong Dữ liệu) của phần tử bạn đang tìm kiếm và là chỉ mục bạn cần để xóa.

Thao tác lặp này dọc theo hàng đợi sẽ làm tăng chỉ số hiệu quả theo số lượng phần tử trước khi nó bị xóa.

Xin lỗi nếu tôi không giải thích rõ ràng, thì rõ ràng trong đầu tôi nhưng khó viết ra.

Bình luận:

• Tiếp cận là O (n), với số n các mặt hàng loại bỏ
• diệt là khoảng gấp đôi so với thời điểm truy cập, nhưng vẫn O (n)
• Một bất lợi là sử dụng bộ nhớ không co lại khi xóa.
• Có khả năng 'tái khởi tạo' khi danh sách bị xóa lớn để đặt lại mức sử dụng bộ nhớ và thời gian truy cập và xóa. Thao tác này lấy O (N), với tổng kích cỡ mảng N.

Vì vậy, nó không hoàn toàn là những gì OP đang tìm kiếm nhưng trong tình huống phù hợp có thể gần gũi.