「数组中出现次数超过一半的数」的技术性专业解决方案(48 字)
-
问题描述
在一个数组中,找到出现次数超过一半的数字。 -
解决方案
算法:摩尔投票法
步骤:
1. 初始化两个变量,一个为计数器,一个为候选数。
2. 遍历数组,如果当前元素与候选数相同,计数器加 1,否则计数器减 1。
3. 如果计数器为 0,重新选择候选数。
4. 遍历结束后,如果计数器不为 0,返回候选数,否则返回 -1。
时间复杂度:O(n)
空间复杂度:O(1)
-
代码实现
python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count, candidate = 0, nums[0]
for num in nums:
if candidate == num:
count += 1
else:
if count == 0:
candidate = num
count = 1
else:
count -= 1
return candidate -
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1) -
应用场景
这种技术性专业解决方案适用于需要处理大量数据并找出出现次数超过一半的数字的场景,例如数据分析、数据库索引等。