My solution to a “Daily Coding Problem” that I received in my mail today.
Given a list of elements, find the majority element, which appears more than half the time (
> floor(len(lst) / 2.0)
).
You can assume that such element exists.
For example, given
[1, 2, 1, 1, 3, 4, 0]
, return 1.
Here’s my solution in,
oneFiftyFive(arr: number[]):number {
if (arr == null || arr == undefined) {
return 0;
}
let half = Math.floor(arr.length / 2);
//find max occurance
let occurenceMap = new Map<number, number>();
let maxOccurence = 0;
for(let i = 0; i < arr.length; i++) {
let n = arr[i];
if(occurenceMap.has(n)) {
let val = occurenceMap.get(n) + 1;
//we get out the moment we find the max occurence
//what if 2 numbers have the same frequency of occurence?
if(val >= half) {
maxOccurence = val;
break;
}
occurenceMap.set(n, val);
} else {
occurenceMap.set(n, 1);
}
}
return maxOccurence;
}
As usual, if you find any of my posts useful support me by buying or even trying one of my apps on the App Store.
Also, if you can leave a review on the App Store or Google Play Store, that would help too.
Categories: ALGORITHMSTYPESCRIPT
Congratulation for the great post. Those who come to read your Information will find lots of helpful and informative tips. Publish IOS App
ReplyDelete