To find the majority element in an array (an element that appears more than ⌊n/2⌋ times), you can use several approaches. One of the most efficient methods is the Boyer-Moore Voting Algorithm, which runs in O(n) time complexity and O(1) space complexity. Here’s a breakdown of how it works and a sample implementation in C#.
Explanation of the Boyer-Moore Voting Algorithm:
-
Initialization: Start with two variables: one for the candidate element (
candidate
) and one for its count (count
). -
Candidate Selection:
- Traverse the array and for each element:
- If
count
is 0, set thecandidate
to the current element and setcount
to 1. - If the current element is the same as the
candidate
, increment thecount
. - If it’s different, decrement the
count
.
- If
- This process effectively cancels out pairs of different elements, and by the end of the traversal, if a majority element exists, it will be stored in
candidate
.
- Traverse the array and for each element:
-
Verification: After finding the candidate, you should verify that it is indeed the majority element by counting its occurrences in the array.
Sample Code:
using System;
class MajorityElementFinder
{
public static int FindMajorityElement(int[] nums)
{
int candidate = 0;
int count = 0;
// Step 1: Find the candidate
foreach (int num in nums)
{
if (count == 0)
{
candidate = num;
count = 1;
}
else if (num == candidate)
{
count++;
}
else
{
count--;
}
}
// Step 2: Verify that the candidate is the majority element
count = 0;
foreach (int num in nums)
{
if (num == candidate)
{
count++;
}
}
return count > nums.Length / 2 ? candidate : -1; // Return -1 if no majority element
}
static void Main()
{
int[] nums = { 3, 2, 3 };
int majorityElement = FindMajorityElement(nums);
if (majorityElement != -1)
{
Console.WriteLine($"The majority element is: {majorityElement}");
}
else
{
Console.WriteLine("No majority element found.");
}
}
}
How It Works:
-
Candidate Selection:
- As you loop through the array, you adjust the
count
based on the current number compared to thecandidate
. - This process finds a potential majority candidate by the end of the first loop.
- As you loop through the array, you adjust the
-
Verification:
- The second loop counts how many times the
candidate
appears in the array to ensure it is indeed a majority element.
- The second loop counts how many times the
-
Output:
- If the count of the candidate is greater than half the length of the array, it is returned; otherwise, -1 is returned to indicate no majority element exists.
Time Complexity:
- O(n): Each loop runs through the array once.
- O(1): Only a constant amount of space is used for variables.
This method is efficient and particularly well-suited for large datasets where space and time efficiency is crucial.