作者:子华2502924833 | 来源:互联网 | 2023-10-09 19:18
本文主要介绍关于算法,数据结构,c++的知识点,对【数组中出现次数超过一半的数字】和【挑战程序员同学】有兴趣的朋友可以看下由【安河桥畔】投稿的技术文章,希望该技术和经验能帮到你解决你所遇的每日一题相关
本文主要介绍关于算法,数据结构,c++的知识点,对【数组中出现次数超过一半的数字】和【挑战程序员同学】有兴趣的朋友可以看下由【安河桥畔】投稿的技术文章,希望该技术和经验能帮到你解决你所遇的每日一题相关技术问题。
挑战程序员同学
数组中出现次数超过一半的数字 题目来源
牛客网:数组中出现次数超过一半的数字
题目描述
给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
数据范围:n≤50000,数组中元素的值 0≤val≤10000
要求:空间复杂度:O(1),时间复杂度 O(n)
输入描述
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.
示例1
输入
[1,2,3,2,2,2,5,4,2]
返回值
2
示例2
输入
[3,3,3,3,2,2,2]
返回值
3
示例3
输入
[1]
返回值
1
思路分析 解法一 抵消法如果两个数不相等,就消去这两个数,最坏情况下,每次消去一个众数和一个非众数,那么如果存在众数,最后留下的数肯定是众数定义一个ret保存当前的众数,定义times表示其出现的次数遍历数组,当前数组值与ret相等则增加times值,不相等则减小times值,times值为0时用当前数组元素的值替换ret 解法二 对数组进行排序找数组中间的数,因为一个数如果在数组中存在次数超过一半,则排序后数组中间的数一定是这个数 代码展示 解法一
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int times = 1;
int ret = numbers[0];
int sz = numbers.size();
for (int i = 1; i < sz; i++)
{
if (times != 0)
{
if (numbers[i] != ret)
{
times--;
}
else
{
times++;
}
}
else
{
ret = numbers[i];
times = 1;
}
}
return ret;
}
};
解法二
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
sort(numbers.begin(),numbers.end());
int sz=numbers.size();
int max=numbers[sz/2];
return max;
}
};
暑期编程PK赛
得CSDN机械键盘等精美礼品!
本文《数组中出现次数超过一半的数字》版权归安河桥畔所有,引用数组中出现次数超过一半的数字需遵循CC 4.0 BY-SA版权协议。