Algorithm
Problem Name: 169. Majority Element
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 * 104-109 <= nums[i] <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int majorityElement(int num[], int n) {
int major;
int i;
major = num[0];
int count = 1;
for (i = 1; i < n; i++) {
if (num[i] == major) count ++;
else count --;
if (count == 0) {
major = num[i];
count = 1;
}
}
return major;
}
int main() {
int num1[] = { 1, 2, 2, 3, 3, 3, 3, 4};
int num2[] = { 4, 5, 4};
printf("%d\n", majorityElement(num1, sizeof(num1)/sizeof(num1[0])));
printf("%d\n", majorityElement(num2, sizeof(num2)/sizeof(num2[0])));
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map < int, int>m;
for(auto x: nums) if(++m[x] > nums.size()/2) return x;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int majorityElement(int[] nums) {
int majorityElement = nums[0];
int count = 0;
for (int num : nums) {
if (count == 0) {
majorityElement = num;
}
count += num == majorityElement ? 1 : -1;
}
return majorityElement;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const majorityElement = function(nums) {
const hash = {};
nums.forEach(el => {
if (hash.hasOwnProperty(el)) {
hash[el] += 1;
} else {
hash[el] = 1;
}
});
return Object.entries(hash)
.filter(el => el[1] > Math.floor(nums.length / 2))
.map(el => +el[0])
.sort((a, b) => b - a)[0];
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
num_list=dict()
for num in nums:
if not num in num_list:
num_list[num]=1
else:
num_list[num]+=1
return max(num_list, key=num_list.get)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0169_MajorityElement
{
public int MajorityElement(int[] nums)
{
int count = 0, candidate = 0;
foreach (var num in nums)
{
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
}
Input
Output