LeetCode Python/Java/C++/JS > 169. Majority Element > Solved in Python, Ruby, Java > GitHub
LeetCode link: 169. Majority Element, difficulty: Easy.
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.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9
Follow-up: Could you solve the problem in linear time and in O(1) space?
Topics
Hint 1
How to solve the problem in O(1) space?
Please search Boyer-Moore majority vote algorithm.
Intuition
The key to solving this problem is to use a hash table to store the occurrence count of each num. The key is the num, and the value is the number of times it appears.
👋 Hi, I'm the developer behind coder.id — Build your programmer brand. Create your portfolio, resume, and blog in minutes, and land your dream offer!
Complexity
Time complexity
O(N)
Space complexity
O(N)
Python #
class Solution:
def majorityElement(self, nums: List[int]) -> int:
num_to_count = defaultdict(int)
for num in nums:
num_to_count[num] += 1
if num_to_count[num] >= len(nums) / 2:
return num
Ruby #
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
num_to_count = Hash.new(0)
nums.each do |num|
num_to_count[num] += 1
if num_to_count[num] > nums.size / 2
return num
end
end
end
Java #
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> numToCount = new HashMap<>();
for (int num : nums) {
numToCount.put(num, numToCount.getOrDefault(num, 0) + 1);
if (numToCount.get(num) > nums.length / 2) {
return num;
}
}
return -1; // This line won't be reached due to problem constraints
}
}
Other languages
Welcome to contribute code to GitHub repo -> 169. Majority Element. Thanks!Level Up Your Developer Identity
- 📄 Resume, Portfolio & Blog
- 🌐 Custom Domain Binding Supported
- ✨ Premium Subdomain:
https://yourname.coder.id