用Python编程:给定一个大小为n的数组,找出多数元素。多数元素 是出现次数大于⌊n/2⌋的元素。你可能会认为 数组是非空的,并且多数元素始终存在于数组中。 注意,如果为数组n使用额外的存储空间,则只能得到1.5 'Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2
时间: 2024-02-25 09:55:34 浏览: 28
可以使用摩尔投票算法来解决这个问题。该算法的基本思想是遍历数组,记录一个候选元素和它出现的次数,如果遍历到的元素和候选元素相同,则增加计数器,否则减少计数器。当计数器归零时,将候选元素更新为当前元素并将计数器置为1。最后剩下的候选元素就是多数元素。
以下是用 Python 实现的代码:
```python
def majority_element(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
```
这个函数接受一个数组作为参数,返回多数元素。它使用了常数级别的额外空间,并且只需要一次遍历,时间复杂度为 O(n)。