Tôi được hỏi trong một cuộc phỏng vấn để đưa ra thuật toán O (n) để in một phần tử xuất hiện nhiều hơn n/2 lần trong một mảng, nếu có một yếu tố như vậy. n là kích thước của mảng. Tôi không có bất kỳ đầu mối nào về cách thực hiện việc này. Có ai giúp được không?Thuật toán O (n) để tìm ra phần tử xuất hiện nhiều hơn n/2 lần
Đó là Boyer's Voting algorithm.
Nó cũng là O (1) trong không gian !.
Sửa
Đối với những phàn nàn về kế hoạch trang web màu (như tôi) ... here is the original paper.
Lược đồ màu trên liên kết đó thật khủng khiếp. –
Dưới đây là một số thông tin khác: http://stackoverflow.com/questions/780937/linear-time-voting-algorithm-i-dont-get-it – chrisaycock
Đọc tốt. Đã cho tôi một phút để tìm ra logic tinh tế giúp tránh duy trì số lượng độc lập: "..._ tăng hoặc giảm số đếm ngược theo e là ứng cử viên hiện tại ..." –
Trong psuedocode:
int n = array.length
Hash<elementType,int> hash
foreach element in array
hash[element] += 1
foreach entry in hash
if entry.value > n/2
print entry.key
break
Điều này có được coi là O (2n) không? –
O (2n) == O (n) Tôi tin – Samuel
@Eric Đây sẽ là 'O (n + m)'. Nhân tiện, không có thứ gì như "O (2n)" khi big-O không sử dụng các hệ số không đổi; trong trường hợp này, nó chỉ là 'O (n)'. – chrisaycock
Nó cũng là giá trị trung bình, trong đó có O (n) để tìm cách sử dụng median-of-medians algorithm. Trong C++, bạn có thể thực hiện điều này trong một dòng:
std::nth_element(begin, begin + n/2, begin + n)
Lưu ý rằng mặc dù 'std :: nth_element' chỉ được yêu cầu để được mong đợi O (n) và do đó có khả năng không sử dụng thuật toán trung vị-trung bình. Việc lựa chọn nhanh như sắp xếp có xu hướng tốt hơn trong thực tế so với m-of-m. –
Bạn có thể sử dụng hàm băm và đếm số phần tử khi quét qua mảng không? – chrisaycock
Không chắc chắn. Tôi nghĩ rằng nên có một giải pháp đơn giản và thanh lịch hơn. – devnull
Ồ. Bạn đã không yêu cầu thanh lịch nhất, chỉ cần O (n) – Samuel