面试题 17.10. 主要元素(C++)
2023-09-14 09:05:15 时间
面试题 17.10. 主要元素
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
我的代码
C++
// 解析:这个题就是一个统计每个数字出现频率的简单题
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> mp;
for (auto num:nums) // 统计每个数字的频率
{
mp[num] ++;
}
for(auto itm:mp) // 然后再遍历哈希表 然后寻找出现频率超过一半的数字
{
if (itm.second >= ((int)nums.size() + 1) / 2) return itm.first; // 这里有个小细节就是需要在除以2之前+1
}
return -1;
}
};
Java
class Solution {
public int majorityElement(int[] nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
int length = nums.length;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
return count * 2 > length ? candidate : -1;
}
}
C
int majorityElement(int* nums, int numsSize) {
int candidate = -1;
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (count == 0) {
candidate = nums[i];
}
if (nums[i] == candidate) {
count++;
} else {
count--;
}
}
count = 0;
int length = numsSize;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == candidate) {
count++;
}
}
return count * 2 > length ? candidate : -1;
}
相关文章
- 【转】一次前端面试题
- 2019年最新阿里Java工程师面试题
- PHP经典面试题:如何保证缓存与数据库的双写一致性?
- Java高级面试题及答案
- (剑指Offer)面试题48:不能被继承的类
- (剑指Offer)面试题39:判断平衡二叉树
- 微软面试题:利用天平砝码,三次将140克的盐 分成50、90克两份?
- (剑指Offer)面试题48:不能被继承的类
- Leetcode 面试题 17.11. 单词距离(medium)
- PHP面试题:使用PHP描述快速排序算法,对象可以是一个数组?
- android 部分中高级面试题以及答案
- 100道c/c++面试题
- 挑战10个最难的Java面试题(附答案)【下】
- 各大厂算法岗面试题汇总之C++篇
- c++程序猿经典面试题
- 计算机网络高频面试题解析(含书籍推荐)
- 【经典面试题】实现平方根函数sqrt
- 2022非常全的接口测试面试题及参考答案【保存下来慢慢刷】
- 算法工程师面试题十一之熵
- 算法工程师面试题一之梯度下降算法
- C/C++经典面试题二
- C/C++经典面试题一
- Android/Java面试题,边面试边成长,为了应试而应试