169. Majority Element@python
2021-06-16 09:05
标签：nbsp 数组 may ble exist log python always time Given an array of size n, find the majority element. The majority element is the element that appears more than You may assume that the array is non-empty and the majority element always exist in the array. 原题地址: Majority Element 难度: Easy 题意: 找出数量超过数组长度一半的值 思路1: 对数组进行排序, 由于某个值的数量超过数组长度的一半,排序之后,数组中间的值必然是要求的结果 代码: 时间复杂度: O(nlog(n)),即排序的复杂度 空间复杂度: O(1) 思路2: 遍历数组,进行统计 时间复杂度: O(n) 空间复杂度: O(n) 思路3: 摩尔投票法: 将数组中不同两个数配成对 代码: 时间复杂度: O(n) 空间复杂度: O(1) 169. Majority Element@python 标签：nbsp 数组 may ble exist log python always time 原文地址：https://www.cnblogs.com/chimpan/p/9726496.html? n/2 ? times.class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums)/2]
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
d = {}
for num in nums:
d[num] = d.get(num, 0) + 1
if d[num] > len(nums) / 2:
return num
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
count = 1
num = nums[0]
for i in range(1, n):
if nums[i] == num:
count += 1
elif count == 0:
num = nums[i]
count += 1
else:
count -= 1
count = 0
for i in range(n):
if nums[i] == num:
count += 1
if count > n / 2:
return num
文章标题：169. Majority Element@python
文章链接：http://soscw.com/index.php/essay/94524.html