Description:
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Examples:
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2Solution in Python:
To solve the problem of finding the majority element in an array, we can use the Boyer-Moore Voting Algorithm. This algorithm is efficient with a time complexity of O(n) and a space complexity of O(1).
Python
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# Initialize the candidate for majority element and a counter
candidate = None
count = 0
# Iterate through the array to find the potential majority element
for num in nums:
if count == 0:
candidate = num # Set the current element as the new candidate
count = 1 # Reset count to 1
elif num == candidate:
count += 1 # Increment count if the current element matches the candidate
else:
count -= 1 # Decrement count if the current element does not match the candidate
# Return the candidate as the majority element
return candidate
# Example usage:
solution = Solution()
print(solution.majorityElement([3,2,3])) # Output: 3
print(solution.majorityElement([2,2,1,1,1,2,2])) # Output: 2Explanation:
- Boyer-Moore Voting Algorithm:
- The algorithm uses two variables:
candidateto store the potential majority element andcountto keep track of the balance between the occurrences of the candidate and other elements. - We iterate through the array. For each element:
- If
countis zero, we set thecandidateto the current element and resetcountto one. - If the current element is equal to the
candidate, we incrementcount. - If the current element is different from the
candidate, we decrementcount.
- If
- The algorithm uses two variables:
- Final Majority Element:
- After one pass through the array, the
candidatewill be the majority element because it appears more than ⌊n / 2⌋ times.
- After one pass through the array, the
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
// Initialize the candidate for majority element and a counter
let candidate = null;
let count = 0;
// Iterate through the array to find the potential majority element
for (let i = 0; i < nums.length; i++) {
if (count === 0) {
candidate = nums[i]; // Set the current element as the new candidate
count = 1; // Reset count to 1
} else if (nums[i] === candidate) {
count++; // Increment count if the current element matches the candidate
} else {
count--; // Decrement count if the current element does not match the candidate
}
}
// Return the candidate as the majority element
return candidate;
};
// Example usage:
console.log(majorityElement([3, 2, 3])); // Output: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // Output: 2Solution in Java:
Java
class Solution {
public int majorityElement(int[] nums) {
// Initialize the candidate for majority element and a counter
int candidate = 0;
int count = 0;
// Iterate through the array to find the potential majority element
for (int num : nums) {
if (count == 0) {
candidate = num; // Set the current element as the new candidate
count = 1; // Reset count to 1
} else if (num == candidate) {
count++; // Increment count if the current element matches the candidate
} else {
count--; // Decrement count if the current element does not match the candidate
}
}
// Return the candidate as the majority element
return candidate;
}
// Example usage:
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.majorityElement(new int[]{3, 2, 3})); // Output: 3
System.out.println(solution.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2})); // Output: 2
}
}Solution in C#:
C#
public class Solution {
public int MajorityElement(int[] nums) {
// Initialize the candidate for majority element and a counter
int candidate = 0;
int count = 0;
// Iterate through the array to find the potential majority element
foreach (int num in nums) {
if (count == 0) {
candidate = num; // Set the current element as the new candidate
count = 1; // Reset count to 1
} else if (num == candidate) {
count++; // Increment count if the current element matches the candidate
} else {
count--; // Decrement count if the current element does not match the candidate
}
}
// Return the candidate as the majority element
return candidate;
}
}