One Pager Cheat Sheet
- The majority element of an array of length
100000
, containing integer values between-1000000000
and1000000000
, can be found inO(n)
time andO(n)
space. - The
majority
element is not the number with the most occurrences, but rather the one with more than50%
of the total "occurrences". - By using a
hash map
to store unique values and their count, it is possible to find the majority element with anO(n)
time complexity andO(n)
space complexity.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
44
}
var assert = require('assert');
​
/**
* @param {number[]} nums
* @return {number}
*/
function majorityElement(nums) {
var sortedNums = nums.sort();
return sortedNums[Math.floor(nums.length / 2)];
}
​
// console.log(majorityElement([1, 1, 1, 4, 2, 4, 4, 3, 1, 1, 1]));
​
try {
assertIsFunction(majorityElement, '`majorityElement` is a function');
​
console.log('PASSED: ' + '`majorityElement` is a function');
} catch (err) {
console.log(err);
}
​
try {
assert.equal(majorityElement([1, 4, 2, 4, 4, 3, 4]), 4);
​
console.log(
'PASSED: ' + '`majorityElement([1, 4, 2, 4, 4, 3, 4])` should return `4`'
);
} catch (err) {
console.log(err);
}
​
try {
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.