Majority Element II
very nice one. The code considers everything and everything looks perfect!!!
Hi, I think we can ignore checking counts[i] > 0 at this line:
Correct if i am wrong, thanks.
@leaper We should make sure y and z point to different numbers, if let if (!cy) .. if (!cz)... first at first y and z are both a, you can check this test case [8,8,7,7,7] for example.
It's a wrong solution!
I donot think so, if the case is [n/4], it should keep three numbers instead of 2. the space complexity should be O(m) where m is the division-1.
Actually you don't need the last loop and you can do that in the second last loop
this is an accurate representation of my frustration right now!
No one has replied
Thank you for the explaination. Now I got it
The code is elegant and have good scalability.
@liangchuanzou The average recursion depth shouldn't be O(log n) I think, because it stops early. Although I'm not sure what's the exact space complexity.
That's because “num == elements[i]” should be checked separately before "!counters[i]", so that the helper slots will not have duplicates.
I rewrite the remove part to make it simpler.
O(1) space if you replace
len([0 for num in nums if num == a])
sum(1 for num in nums if num == a) # generators ftw
Make sense!! Everything is a balance of cost and reliability including algorithms. When reliability is good enough, we need to try best to lower cost. I now think a 2e-18 possibility is good enough.
@massic Since the question is to find all elements that appear more than ⌊ n/3 ⌋ times, we know there would be at most 2 elements. We first get the two biggest numbers and then judge if any of them satisfies the condition.
Disabled Categories are greyed out
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.