数组中出现次数超过一半的数字
数组 数字 出现 次数 超过 一半
2023-09-14 09:08:54 时间
数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
int cmp(pair<int,int>&a,pair<int,int>&b){
return a.second<b.second;
}
int main(){
int num;
vector<pair<int,int> >vec;
cin>>num;
map<int,int> mymap;
mymap[num]++;
while (cin.get()!='\n')
{
cin>>num;
mymap[num]++;
}
for (map<int,int>::iterator it=mymap.begin(); it != mymap.end(); it++)
{
vec.push_back(*it);
}
sort(vec.begin(),vec.end(),cmp);
// for (int i = 0; i < vec.size(); i++)
// {
// cout<<vec[i].first<<" "<<vec[i].second<<endl;
// }
cout<<vec[vec.size()-1].first<<endl;
}
解题思路:
本题常见解法如下:
哈希表统计法: 遍历数组 nums ,用 HashMap 统计各数字的数量,最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N) 。
数组排序法: 将数组 nums 排序,由于众数的数量超过数组长度一半,因此 数组中点的元素 一定为众数。此方法时间复杂度 O(Nlog 2N)。
摩尔投票法: 核心理念为 “正负抵消” ;时间和空间复杂度分别为 O(N) 和 O(1) ;是本题的最佳解法
摩尔投票法:
票数和: 由于众数出现的次数超过数组长度的一半;若记 众数 的票数为 +1 ,非众数 的票数为 -1 ,则一定有所有数字的 票数和 > 0 。
票数正负抵消: 设数组 nums 中的众数为 x ,数组长度为 n 。若 nums 的前 a 个数字的 票数和 = 0x,则 数组后 (n-a)个数字的 票数和一定仍 >0 (即后 (n-a)个数字的 众数仍为 x)。
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
}
题目拓展:
由于题目明确给定 给定的数组总是存在多数元素 ,因此本题不用考虑 数组中不存在众数 的情况。
若考虑,则需要加入一个 “验证环节” ,遍历数组 nums 统计 x 的数量。
若 x 的数量超过数组长度一半,则返回 x ;
否则,返回 0 (这里根据不同题目的要求而定)。
时间复杂度仍为 O(N),空间复杂度仍为 O(1) 。
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0, count = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
// 验证 x 是否为众数
for(int num : nums)
if(num == x) count++;
return count > nums.length / 2 ? x : 0; // 当无众数时返回 0
}
}
相关文章
- get请求包含参数属性为数组
- 数组中的重复数字
- es6数组和对象常用方法
- 剑指 Offer 03. 数组中重复的数字(原地算法)「建议收藏」
- 154. 寻找旋转排序数组中的最小值 II
- 集合转数组的方法_数组的定义方式
- c-计蒜客 排序好的数组删除重复数字
- 【Excel新函数】动态数组系列
- C++ 数组
- 2022-12-22:给定一个数字n,代表数组的长度, 给定一个数字m,代表数组每个位置都可以在1~m之间选择数字, 所有长度为n的数组中,最长递增子序列长度为
- 剑指40-数组中只出现一次的数字
- 2022-12-22:给定一个数字n,代表数组的长度,给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,所有长度为n的
- 剑指offer|03. 数组中重复的数字
- 剑指 Offer 03. 数组中重复的数字
- 【剑指offer|5.在排序数组中查找数字I】
- 每日一题:数组中数字出现的次数2
- LeetCode每日一练:数组中重复的数字
- mongodb 数据类型(null/字符串/数字/日期/内嵌文档/数组等)
- 认识JAVA数组详解编程语言
- javascript二维数组操作详解编程语言
- MySQL简易使用数组参数进行操作(mysql数组参数)
- MySQL函数:处理数组的利器(mysql函数数组)
- Oracle中的低数组使用细则(oracle低基数列)
- java中文字符串数组按照音序排列
- Javascript去除数组的重复元素
- perl数组的多数字下标示例代码