Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
时间: 2024-03-14 16:45:28 浏览: 16
To solve this problem, we can use Boyer-Moore Voting Algorithm, which runs in O(n) time complexity and O(1) space complexity.
The idea behind this algorithm is to cancel out all occurrences of an element e that is not the majority element and count the remaining element as the majority element.
Here is the implementation of the algorithm in Python:
```
def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
```
In the above code, we first initialize the count and candidate variables to 0 and None respectively. Then, we loop through the array and check if the count is 0, if it is, we set the candidate to the current element. We then increment the count if the current element is the candidate, otherwise we decrement it.
At the end of the loop, the candidate variable will hold the majority element.