85 lines
1.9 KiB
Markdown
85 lines
1.9 KiB
Markdown
|
|
|||
|
|
## 题目地址
|
|||
|
|
https://leetcode.com/problems/majority-element/description/
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
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
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
符合直觉的做法是利用额外的空间去记录每个元素出现的次数，并用一个单独的变量记录当前出现次数最多的元素。
|
|||
|
|
|
|||
|
|
但是这种做法空间复杂度较高，有没有可能进行优化呢？ 答案就是用"投票算法"。
|
|||
|
|
|
|||
|
|
投票算法的原理是通过不断消除不同元素直到没有不同元素，剩下的元素就是我们要找的元素。
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 关键点解析
|
|||
|
|
|
|||
|
|
- 投票算法
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
* 语言支持：JS，Python
|
|||
|
|
|
|||
|
|
Javascript Code:
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
var majorityElement = function(nums) {
|
|||
|
|
let count = 1;
|
|||
|
|
let majority = nums[0];
|
|||
|
|
for(let i = 1; i < nums.length; i++) {
|
|||
|
|
if (count === 0) {
|
|||
|
|
majority = nums[i];
|
|||
|
|
}
|
|||
|
|
if (nums[i] === majority) {
|
|||
|
|
count ++;
|
|||
|
|
} else {
|
|||
|
|
count --;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return majority;
|
|||
|
|
};
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Python Code:
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
class Solution:
|
|||
|
|
def majorityElement(self, nums: List[int]) -> int:
|
|||
|
|
count, majority = 1, nums[0]
|
|||
|
|
for num in nums[1:]:
|
|||
|
|
if count == 0:
|
|||
|
|
majority = num
|
|||
|
|
if num == majority:
|
|||
|
|
count += 1
|
|||
|
|
else:
|
|||
|
|
count -= 1
|
|||
|
|
return majority
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**复杂度分析**
|
|||
|
|
- 时间复杂度：$O(N)$，其中N为数组长度
|
|||
|
|
- 空间复杂度：$O(1)$
|
|||
|
|
|
|||
|
|
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
|
|||
|
|
|
|||
|
|
|