Bạn sẽ chọn một phần tử ngẫu nhiên đồng nhất trong danh sách được liên kết với độ dài không xác định trong một lần chuyền hoặc nếu không phải là hai vé?Bạn sẽ chọn một phần tử ngẫu nhiên đồng nhất trong danh sách được liên kết với độ dài không xác định như thế nào?
Sử dụng lấy mẫu hồ chứa http://en.wikipedia.org/wiki/Reservoir_sampling. Bạn chỉ cần một lần truyền dữ liệu.
Đối chọn một phần tử:
Tôi sẽ cho phép bạn chứng minh rằng kết quả này trong việc lựa chọn đồng đều các phần tử.
Tôi đã cố gắng sử dụng nhưng điều này sẽ chọn k phần tử ngẫu nhiên. nhưng tôi sẽ chỉ cần chọn phần tử đầu tiên – exlux15
@AnilBabooram Sử dụng k = 1? Dù sao, thuật toán được đề cập trong bài viết (không phải wiki) là cho một trường hợp phần tử. – ElKamina
ok nếu tôi sử dụng vòng lặp while dọc theo độ dài ++ để duyệt qua danh sách. Nếu tôi sử dụng i = rand()% length, "i" có phải là lựa chọn ngẫu nhiên tại nút hiện tại không? – exlux15
Tôi e rằng bạn sẽ phải nỗ lực nhiều hơn một chút trong câu hỏi của mình và làm cho nó rõ ràng những gì bạn đang yêu cầu –
ok. làm thế nào bạn sẽ chọn một phần tử ngẫu nhiên đồng nhất trong danh sách liên kết với độ dài không xác định? – exlux15
Nếu đó là câu hỏi của bạn, đó là một câu hỏi thú vị. Xin vui lòng chỉnh sửa câu hỏi của bạn cho phù hợp và tôi sẽ upvote nó –