You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The current implemented algorithm which finds the majority element of an array is the Moore-Voting algorithm. However, there are a few other ways to solve this problem which I believe must be a part of this repository. One of them is using a randomized algorithm. On average it has the same runtime, but when the size of the array increases exponentially, this algorithm is much much faster probabilistically.
The majority element of a vector is an element which occurs with a frequency more than floor(n/2). So you have more than a 50% chance of picking out the majority element in your first try if you pick any element randomly.
Suppose you don't find the majority element in your first try. You can then pick a random element again and check if it is a majority element. You do this until you eventually find the majority element.
The algorithm is verifiably correct because we ensure that the randomly chosen value is the majority element before ever returning. I believe that this algorithm must be a part of this repository
The text was updated successfully, but these errors were encountered:
This is O(n):
Details:
The current implemented algorithm which finds the majority element of an array is the Moore-Voting algorithm. However, there are a few other ways to solve this problem which I believe must be a part of this repository. One of them is using a randomized algorithm. On average it has the same runtime, but when the size of the array increases exponentially, this algorithm is much much faster probabilistically.
The majority element of a vector is an element which occurs with a frequency more than floor(n/2). So you have more than a 50% chance of picking out the majority element in your first try if you pick any element randomly.
Suppose you don't find the majority element in your first try. You can then pick a random element again and check if it is a majority element. You do this until you eventually find the majority element.
The algorithm is verifiably correct because we ensure that the randomly chosen value is the majority element before ever returning. I believe that this algorithm must be a part of this repository
The text was updated successfully, but these errors were encountered: