Tìm giữa danh sách kích thước không xác định

Question

Trong một cuộc phỏng vấn gần đây tôi đã được hỏi:

Tìm phần tử trung bình của danh sách được sắp xếp có độ dài chưa biết bắt đầu từ vị trí đầu tiên.

Tôi đáp lại bằng này:

Có 2 quầy số các mục:

counter1 counter2

Tăng counter1 bởi 1 và counter2 bằng 2. Khi truy cập 2 đạt đến cuối danh sách truy cập 1 sẽ ở giữa. Tôi cảm thấy rằng điều này không hiệu quả vì tôi đang xem lại các nút mà tôi đã thấy. Dù bằng cách nào, là có một thuật toán hiệu quả hơn?

Answer 1

Giả sử danh sách được liên kết, bạn có thể làm điều đó trong khi truy cập tùy tiện gần với N của các mục.

Để làm được 5/4 N:

• lặp trên danh sách cho đến khi bạn nhấn cuối cùng, đếm các mục.
• Thả neo ở mọi quyền của phần tử 2'th. Theo dõi 2 neo cuối cùng.
• Lặp lại neo trước đó cho đến khi nó đến giữa danh sách.

Khi bạn nhấn vào cuối danh sách, neo trước đó trước điểm giữa nhưng ít nhất là một nửa đã có. Vì vậy, N cho lặp lại đầy đủ + nhiều nhất là 1/4 N cho neo = 5/4 N.

Thả neo thường xuyên hơn, chẳng hạn như ở mọi công suất trần 1,5^mục, giúp bạn gần với N cần thiết (với chi phí theo dõi nhiều neo hơn; nhưng đối với bất kỳ X nào là bước điện, bộ nhớ tiệm cận là không đổi).

Answer 2

Giả sử bạn có thể phát hiện rằng bạn vượt quá danh sách và tìm kiếm vị trí tùy ý trong danh sách, bạn có thể tăng gấp đôi độ dài được liệt kê của danh sách (đoán chiều dài là 1, sau đó 2, rồi 4 , ...) cho đến khi bạn kết thúc danh sách, sau đó sử dụng tìm kiếm nhị phân giữa giá trị được thử cuối cùng nhỏ hơn độ dài của danh sách và giá trị đầu tiên vượt quá cuối danh sách để tìm kết thúc thực tế của danh sách.

Sau đó, tìm kiếm vị trí END_OF_LIST/2.

Bằng cách đó, bạn không phải truy cập mọi nút.

Answer 3

Tôi cho rằng bạn đang thảo luận về danh sách được liên kết. Thật vậy giải pháp của bạn là một giải pháp tuyệt vời. Một thay thế sẽ chỉ đơn giản là đi qua danh sách đếm số lượng các phần tử, và sau đó bắt đầu lại từ đầu, vượt qua một nửa số lượng được đếm. Cả hai phương pháp đều kết thúc các nút 3n/2, vì vậy không có nhiều khác biệt.

Có thể có các ưu điểm bộ nhớ cache nhỏ cho một trong hai phương pháp tùy thuộc vào kiến ​​trúc; phương pháp đầu tiên có thể có lợi thế là có các nút được lưu trong bộ nhớ đệm có thể có nghĩa là truy xuất nhanh hơn nếu bộ nhớ cache đủ lớn trước khi hai con trỏ cách nhau hai. Ngoài ra, bộ nhớ cache có thể nhận được các khối tốt hơn nếu chúng ta duyệt qua danh sách trong một lần, thay vì giữ hai con trỏ còn sống.

Answer 4

Về mặt kỹ thuật, bạn có thể thực hiện điều này trong một lần truyền tải nếu bạn sử dụng bộ nhớ O (N) (giả sử bạn đang sử dụng danh sách được liên kết).

1. Chuyển danh sách và chuyển đổi nó thành một mảng (con trỏ nếu đây là danh sách được liên kết).
2. Mảng trả về [N/2]

Chỉnh sửa: Tôi yêu câu trả lời của bạn!

Answer 5

Giả sử thường xuyên trong bộ nhớ danh sách liên kết cho phép đọc các phần tử tiếp theo được tham chiếu đến nhiều lần hiện tại (từ chối trách nhiệm, không kiểm tra, nhưng ý tưởng nên làm việc):

// assume non-empty list 
slow = fast = first; 
count = 0; 

while (fast) 
{ 
    fast = fast.next; 

    if (!fast) 
    break; 

    count++; 
    fast = fast.next; 

    if (fast) 
    count++; 

    slow = slow.next; 
} 

if (count % 2) 
    return slow.data; 
else 
    return (slow.data + slow.next.data)/2.0; 

Một trường hợp khó khăn hơn là khi "danh sách" không phải là danh sách được liên kết trong bộ nhớ, mà là một luồng mà bạn có thể đọc theo thứ tự được sắp xếp và chỉ đọc từng phần tử một lần mà tôi không có giải pháp tốt.