#P4036. 多数元素
-
ID: 2252
Tried: 33
Accepted: 19
Difficulty: 6
-
算法标签>思维
多数元素
题目内容
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素
输入描述
输入一个数组
输出描述
输出一个整数表示其中的多数元素
样例1
输入
3 2 3
输出
3
样例2
输入
2 2 1 1 1 2 2
输出
2
提示
- n==nums.length
- 1<=n<=5∗104
- −109<=nums[i]<=109
题解
题面描述
题目要求在一个大小为n的数组nums中寻找多数元素，即出现次数大于⌊n/2⌋的元素。
可以保证数组非空且多数元素一定存在。
思路
由于多数元素出现次数超过数组长度的一半，因此可以采用Boyer-Moore 投票算法。
该算法的核心思路是：
- 定义候选元素和计数器。
- 遍历数组，当计数器为0时，将当前元素设为候选元素，并将计数器设为1；
- 如果后续元素与候选元素相同，则计数器加1，否则计数器减1。
- 最终候选元素就是多数元素。
该算法时间复杂度为O(n)，空间复杂度为O(1)。
代码分析
- 初始化：定义变量candidate和count。
- 遍历数组：若count为0，更新candidate为当前元素；若当前元素与candidate相同则count++，否则count−−。
- 输出：遍历结束后，candidate即为所求的多数元素。
算法本质上通过“抵消”策略，使得最后剩下的候选元素必定为多数元素。
C++
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// 返回数组中的多数元素
int majorityElement(vector<int>& nums) {
int candidate = 0; // 候选元素
int count = 0; // 计数器
for (int num : nums) { // 遍历数组
if (count == 0) { // 如果计数器为0，则更新候选元素
candidate = num;
count = 1;
} else if (num == candidate) { // 当前元素与候选元素相同，计数器加1
count++;
} else { // 否则，计数器减1
count--;
}
}
return candidate;
}
};
int main() {
int x;
vector<int> nums;
// 读取所有输入数字，注意ACM模式下输入由空格或者换行分隔
while (cin >> x) {
nums.push_back(x);
}
Solution sol;
cout << sol.majorityElement(nums) << endl;
return 0;
}
Python
class Solution:
def majorityElement(self, nums):
# 初始化候选元素和计数器
candidate = None # 候选元素
count = 0 # 计数器
# 遍历数组中的每个数字
for num in nums:
if count == 0:
candidate = num # 当计数器为0时，更新候选元素
count = 1
elif num == candidate:
count += 1 # 当前数字与候选元素相同，计数器加1
else:
count -= 1 # 不同则计数器减1
return candidate
if __name__ == '__main__':
import sys
# 读取输入，以空格或换行分隔所有数字
data = sys.stdin.read().strip().split()
nums = list(map(int, data))
sol = Solution()
print(sol.majorityElement(nums))
Java
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
static class Solution {
// 返回数组中的多数元素
public int majorityElement(int[] nums) {
int candidate = 0; // 候选元素
int count = 0; // 计数器
for (int num : nums) { // 遍历数组
if (count == 0) {
candidate = num; // 当计数器为0时，更新候选元素
count = 1;
} else if (num == candidate) {
count++; // 当前数字与候选元素相同，计数器加1
} else {
count--; // 不同则计数器减1
}
}
return candidate;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
// 读取所有输入数字
while (sc.hasNextInt()) {
list.add(sc.nextInt());
}
int n = list.size();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = list.get(i);
}
Solution sol = new Solution();
System.out.println(sol.majorityElement(nums));
sc.close();
}
}