You have an array nums with n elements, and you need to find the majority element. The majority element is the one that appears more than ⌊n / 2⌋ times in the array. For this problem, you can trust that there will always be a majority element in the array.
Input: nums = [3, 2, 3]
Output: 3
Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
he length of nums is between 1 and 50,000 elements.
Each number in nums ranges from -10^9 to 10^9.
function majorityElementBoyer(nums) {
let candidate = null;
let count = 0;
for (const num of nums) {
if (count === 0) {
candidate = num;
}
count += (num === candidate ? 1 : -1);
}
return candidate;
}
const nums1 = [3, 2, 3];
majorityElementBoyer(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementBoyer(nums2); //output: 2
function majorityElementHashMap(nums) {
const counts = new Map();
for (const num of nums) {
counts.set(num, (counts.get(num) || 0) + 1);
if (counts.get(num) > nums.length / 2) {
return num;
}
}
}
const nums1 = [3, 2, 3];
majorityElementHashMap(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementHashMap(nums2); //output: 2
function majorityElementSorting(nums) {
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
}
const nums1 = [3, 2, 3];
majorityElementSorting(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementSorting(nums2); //output: 2
function majorityElementDivideConquer(nums) {
function majorityElementRec(start, end) {
if (start === end) {
return nums[start];
}
const mid = Math.floor((start + end) / 2);
const left = majorityElementRec(start, mid);
const right = majorityElementRec(mid + 1, end);
if (left === right) {
return left;
}
const leftCount = nums.slice(start, end + 1).filter(x => x === left).length;
const rightCount = nums.slice(start, end + 1).filter(x => x === right).length;
return leftCount > rightCount ? left : right;
}
return majorityElementRec(0, nums.length - 1);
}
const nums1 = [3, 2, 3];
majorityElementDivideConquer(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementDivideConquer(nums2); //output: 2
function majorityElement(nums) {
for (let i = 0; i < nums.length; i++) {
let count = 0;
for (let j = 0; j < nums.length; j++) {
if (nums[j] === nums[i]) {
count++;
}
}
if (count > nums.length / 2) {
return nums[i];
}
}
}
const nums1 = [3, 2, 3];
majorityElement(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElement(nums2); //output: 2
function majorityElementCounterObj(nums) {
const count = {};
const majorityCount = nums.length / 2;
for (const num of nums) {
count[num] = (count[num] || 0) + 1;
if (count[num] > majorityCount) {
return num;
}
}
}
const nums1 = [3, 2, 3];
majorityElementCounterObj(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementCounterObj(nums2); //output: 2
function majorityElementBitManipulation(nums) {
const majorityCount = nums.length / 2;
const bitLength = 32; // Assume 32-bit integers
let majority = 0;
for (let bit = 0; bit < bitLength; bit++) {
let count = 0;
for (const num of nums) {
if ((num & (1 << bit)) !== 0) {
count++;
}
}
if (count > majorityCount) {
majority |= (1 << bit);
}
}
return majority;
}
const nums1 = [3, 2, 3];
majorityElementBitManipulation(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementBitManipulation(nums2); //output: 2
function majorityElementPriorityQueue(nums) {
const count = new Map();
const majorityCount = nums.length / 2;
// Count occurrences of each number
for (const num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
// Use a priority queue to find the majority element
const minHeap = [];
count.forEach((value, key) => {
minHeap.push({key, value});
});
minHeap.sort((a, b) => b.value - a.value); // Sort by frequency in descending order
return minHeap[0].key; // Return the majority element
}
const nums1 = [3, 2, 3];
majorityElementPriorityQueue(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementPriorityQueue(nums2); //output: 2
function majorityElementRandomized(nums) {
function findMajority(candidate, nums) {
let count = 0;
for (const num of nums) {
if (num === candidate) {
count++;
}
}
return count > nums.length / 2;
}
let candidate;
while (true) {
candidate = nums[Math.floor(Math.random() * nums.length)];
if (findMajority(candidate, nums)) {
return candidate;
}
}
}
const nums1 = [3, 2, 3];
majorityElementRandomized(nums1); //output: 3
const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementRandomized(nums2); //output: 2
In this approach, you repeatedly sample random elements from the array and check if it is the majority element. This method relies on probabilistic reasoning.