Learner Level
Implement the majorityElementValue method that returns the value that appears more than half of the time.
The input contains an integer array nums and its length size. Your task is to return the majority element.
The majority element is the value that appears more than size / 2 times in the array. For example, in [2,2,1,1,1,2,2], the value 2 appears more than half of the time, so the answer is 2.
Example 1
Input
nums (int[]) =
[2,2,1,1,1,2,2]size (int) =
7Returns (int)
2Example 2
Input
nums (int[]) =
[3,2,3]size (int) =
3Returns (int)
3Example 3
Input
nums (int[]) =
[1,1,1,2,3]size (int) =
5Returns (int)
1This can be solved efficiently using the Boyer-Moore voting algorithm.
Keep one candidate value and a counter. When the counter becomes zero, choose the current value as the new candidate. If the current value matches the candidate, increase the counter; otherwise, decrease it.
Because the majority element appears more than half of the time, all other values cannot fully cancel it out, so the remaining candidate is the answer.
Pseudocode:
function majorityElementValue(nums, size):
candidate = 0
count = 0
for each num in nums:
if count == 0:
candidate = num
if num == candidate:
count++
else:
count--
return candidateReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run