当前位置： 面试刷题>> 主元素Ⅰ (经典算法题500道)
### 题目描述补全：
**主元素Ⅰ**
在一个整数数组`nums`中，如果存在一个数出现的次数大于数组长度的一半，那么这个数就被称为主元素（也称为多数元素）。现在要求你编写一个函数，用于判断给定的整数数组`nums`是否存在主元素，并返回该主元素（如果存在）。如果不存在主元素，则返回`null`或`None`（取决于你使用的编程语言）。
### 示例：
- 输入：`nums = [3, 2, 3]`
- 输出：`3`
- 输入：`nums = [2, 2, 1, 1, 1, 2, 2]`
- 输出：`2`
- 输入：`nums = [1, 2, 3, 4]`
- 输出：`null`（或`None`）
### 解题思路：
一种常见的解题思路是使用摩尔投票算法（Boyer-Moore Voting Algorithm）。该算法的基本思想是，由于主元素出现的次数大于数组长度的一半，因此当遍历数组时，可以不断抵消非主元素，直到找到可能的候选主元素。然后，再次遍历数组验证该候选主元素是否确实满足条件。
### PHP 示例代码：
```php
function majorityElement($nums) {
$candidate = null;
$count = 0;
// Step 1: 找到候选主元素
foreach ($nums as $num) {
if ($count === 0) {
$candidate = $num;
}
if ($num === $candidate) {
$count++;
} else {
$count--;
}
}
// Step 2: 验证候选主元素
$count = 0;
foreach ($nums as $num) {
if ($num === $candidate) {
$count++;
}
}
// 判断是否为主元素
if ($count > count($nums) / 2) {
return $candidate;
}
return null;
}
```
### Python 示例代码：
```python
def majorityElement(nums):
candidate = None
count = 0
# Step 1: 找到候选主元素
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -= 1
# Step 2: 验证候选主元素
count = sum(1 for num in nums if num == candidate)
# 判断是否为主元素
if count > len(nums) // 2:
return candidate
return None
```
### JavaScript 示例代码：
```javascript
function majorityElement(nums) {
let candidate = null;
let count = 0;
// Step 1: 找到候选主元素
for (let num of nums) {
if (count === 0) {
candidate = num;
}
if (num === candidate) {
count++;
} else {
count--;
}
}
// Step 2: 验证候选主元素
count = 0;
for (let num of nums) {
if (num === candidate) {
count++;
}
}
// 判断是否为主元素
if (count > nums.length / 2) {
return candidate;
}
return null;
}
```
**码小课**网站中有更多相关内容分享给大家学习，涵盖各种算法和数据结构的深入解析与实战应用。