Doesn’t this assume that the array consists of two distinct numbers only?
_P_a_o_l_o_
It isn't linear time, but nums.sort() followed by returning nums[len(nums)//2] will work, since in a sorted array, a number that appears MORE than n/2 times HAS to be the midpoint because n/2 + 1 can't exist in a section of the array, left or right of the midpoint that is n/2.
your way is faster though.
green
These kind of “find the trick” questions are terrible for interviews. Good interview questions are ones that require flexing multiple aspects of software engineering such as data structures, memory management, multithreading, and system design.
Jordan
Wouldn't an input of [2, 2, 1, 1, 1, 3, 3] output the incorrect answer 3 using this algorithm?
gavin
The provided code differs from the demonstration in that the candidate updates to “1” when it looks at the 3rd “1”, not the 2nd “1”.
brianjjames
Could you just sort the array and then return the first element of the second half of the array? I know this sounds really stupid but was just a random idea.
Westonpoteat_
Am I missing something here, or wouldn't it be easier to create a map of frequencies and then return the num with most occurrences? You can even use the reduce method. Also O(n).
masomthefoodie
If after the one there's a 3 instead of a 2 the whole algorithm falls apart
Soulxstar
Sort the array using quick sort. That is n*log(n) complexity. That start counting the now sorted array, +1 for every same element. In our example it would be [ 1 1 1 2 2 2 2 ] Every time there is a switch (you go from 1 to 2, aka the current element is different than the next element) you compare your current counter with n/2. If it already is more than n/2 you stop, else reset counter and continue until the next "switch".
Total complexity n*log(n) + n.
The solution proposed by the author would not work with the [2 1 2 1 2 1 2] array. The author is basically computing "switches". between 1 and 2
nagyzoli
these comments are filled with people who dont know the difference between majority and plurality
DDvargas
This does not work. Here, test it yourself:
function majority(a){
let v = a[0];
let c = 1;
for(let i = 1; i < a.length; i++){
c += (v == a[i]) ?1 :(-1);
if(c <= 0) v = a[i];
}
return v;
}
majority([2, 2, 1, 1, 1, 2, 2]) == 2 // as stated in the video
majority([1, 2, 2, 1, 2, 2, 1]) == 1 // which is a different result, but we only rearranged the items in the array
As you can see, the majority function above is not useful. The problem is that is breaks when c < 0, and the vide does not tell you what you're supposed to do in that case. I tried checking c <= 0 instead, but that didn't fix the issue.
simonwillover
for me, the question throws me off. i would prefer a real scenario with the context, not just a random riddle.
for _, num := range nums {
if count == 0 {
candidate = num
}
if num == candidate {
count++
} else {
count--
}
}
// Since a majority element is guaranteed, directly return the candidate
return candidate
}
wij
my solution
import os
os.system('cls' if os.name == 'nt' else 'clear')
class Solution:
def majority_element(self, N):
hashmap = {}
greater = [] # Inicializa com o menor valor possível
for pos, item in enumerate(N):
if item not in hashmap.keys():
hashmap[item] = [item]
else:
hashmap[item].append(item)
if len(hashmap[item]) > len(greater):
greater = hashmap[item]
return greater[0]
They're asking easy questions because they want easy answers. Its like the google telephone pole question, you start trying to answer with maths when all you need is common sense.
