算法随笔_69-多数元素_方法3
目录
算法随笔_69: 多数元素_方法3
上一篇:
=====
题目描述如下:
给定一个大小为
n
的数组
nums
，返回其中的多数元素。多数元素是指在数组中出现次数
大于
⌊ n/2 ⌋
的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2=====
算法思路:
由于题目设定肯定存在多数元素，且多数元素大于n/2。假如我们对数组进行排序，在索引n/2的位置，必然就是这个多数元素。
时间复杂度为O(n log n)。下面是Python代码实现:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
n_2=len(nums)//2
return nums[n_2]