169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

来自 <https://leetcode.com/problems/majority-element/description/>

思路1：记录下每个元素出现的次数，并以键值对的形式存放在字典中，找出次数最高的那个元素

 1 class Solution(object):
 2     def majorityElement(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         m_dict = {}
 8         for i in nums:
 9             if i in m_dict.keys():
10                 m_dict[i] += 1
11             else:
12                 m_dict[i] = 1
13         values = list(m_dict.values())
14         id=values.index(max(values))
15         return list(m_dict.keys())[id]

思路2：对所有元素进行排序，在排序中位于length/2位置上的一定是出现次数超过一半的那个

1 class Solution(object):
2     def majorityElement(self, nums):
3         """
4         :type nums: List[int]
5         :rtype: int
6         """
7         return sorted(nums)[len(nums)//2]