63 lines
1.6 KiB
Markdown
63 lines
1.6 KiB
Markdown
---
|
||
title: leetcode-169
|
||
date: 2020-03-23 23:12:57
|
||
tags:
|
||
categories: leetcode
|
||
---
|
||
|
||
|
||
### 169. 多数元素
|
||
|
||
[题目](https://leetcode-cn.com/problems/majority-element/)
|
||
|
||
|
||
|
||
<!--more-->
|
||
|
||
|
||
|
||
一开始的思路是遍历一遍整个列表，用一个字典去记录每个元素出现的次数，当次数大于 $\cfrac{n}{2}$ 时就可以得出结果。
|
||
|
||
```python
|
||
class Solution:
|
||
def majorityElement(self, nums) -> int:
|
||
d = {}
|
||
l = len(nums)
|
||
for n in nums:
|
||
if not n in d:
|
||
d[n] = 0
|
||
d[n] = d[n] + 1
|
||
if d[n] > l/2:
|
||
return n
|
||
# 64 ms 15.1 MB
|
||
```
|
||
|
||
Python 也有专门计数的库，写起来更简单一点：
|
||
|
||
```python
|
||
class Solution:
|
||
def majorityElement(self, nums):
|
||
counts = collections.Counter(nums)
|
||
return max(counts.keys(), key=counts.get)
|
||
# 44 ms 15.1 MB
|
||
```
|
||
|
||
由于要找的数出现次数大于 $\cfrac{n}{2}$，脑子里掠过一下[蒙特卡罗算法](https://zh.wikipedia.org/wiki/%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%96%B9%E6%B3%95)，后来在官方解答中也看到类似的思路了：
|
||
|
||
```python
|
||
class Solution:
|
||
def majorityElement(self, nums):
|
||
majority_count = len(nums)//2
|
||
while True:
|
||
candidate = random.choice(nums)
|
||
if sum(1 for elem in nums if elem == candidate) > majority_count:
|
||
return candidate
|
||
|
||
#作者：LeetCode-Solution
|
||
#链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
|
||
#来源：力扣（LeetCode）
|
||
#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
||
```
|
||
|
||
|