给定具有n个元素的序列,寻找该序列的多数元素(多数元素是指在序列中出现次数大于[n/2]的元素),若不存在这样的数字则给出“不存在”提示信息。例如,输入9个元素48 0 5 5 5 16 5 5 0 时,输出结果为5。
时间: 2024-02-21 13:00:08 浏览: 119
这是一个经典的问题,可以使用摩尔投票算法来解决。具体步骤如下:
1. 初始化候选元素为序列中的第一个元素,计数器为1。
2. 遍历序列中的每一个元素,如果当前元素与候选元素相同,则计数器加1,否则计数器减1。
3. 如果计数器减为0,则更新候选元素为当前元素,并将计数器重置为1。
4. 重新遍历序列,统计候选元素出现的次数,如果次数大于[n/2],则返回候选元素,否则输出“不存在”。
Python代码实现如下:
```python
def majority_element(nums):
candidate = nums[0]
count = 1
for num in nums[1:]:
if num == candidate:
count += 1
else:
count -= 1
if count == 0:
candidate = num
count = 1
count = 0
for num in nums:
if num == candidate:
count += 1
if count > len(nums) // 2:
return candidate
else:
return "不存在"
```
对于输入的序列48 0 5 5 5 16 5 5 0,调用该函数后输出结果为5。