《剑指offer》数组中出现次数超过一半的数字
2024-08-31 11:17:14
一、题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
二、输入描述
输入一个数组
三、输出描述
超过数组长度的一半的数,如果没有输出0
四、牛客网提供的框架
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
}
};
五、解题思路
这是2013年腾讯招聘题目。以下是《王道求职宝典》的方法:
1)初始化:设当前的数组为data[],数组的长度为n。currentAxis=data[0],currentNum=1;
2)设i=1,遍历数组,转向3;
3)当data[i]==currentNum==0时,currentNum++,转向5;否则转向4;
4)currentNum–,当currentNum==0时,currentAxis=data[i];
5)当i==data.length时,转向(6);否则i++,转向3;
6)再次遍历数组中值为currentAxis的个数是否超过数组长度的一半;转向7;
7)如果是输出currentAxis,否则输出0;
六、代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size() < 1) return 0;
if(numbers.size() == 1) return numbers[0];
int numCount = 1;
int temp = numbers[0];
for(int i = 1; i < numbers.size(); i++)
{
if(numCount <= 0){temp = numbers[i]; numCount = 1;}
if(numbers[i] == temp) numCount++;
else numCount--;
}
int num = 0; //检查值为temp的个数是否超过数组长度的一半
for(int i = 0; i < numbers.size(); i++)
{
if(numbers[i] == temp) num++;
}
if(numCount > 0 && num > numbers.size()/2) return temp;
else return 0;
}
};
最新文章
- CRM Setstate plugin
- mysql explain 命令讲解
- linux运维工程师
- jsp日期控件My97DatePicker的使用
- Apache log4cxx用法
- UVA - 10129 Play on Words(欧拉回路+并查集)
- poj1799---解析几何
- ibatis配置log4j输出sql日志信息
- oracle排序的几种方法
- 【Python】正则表达式re
- APP测试要点—UI、功能测试
- 从CAP理论中分析Eureka与zookeeper的区别
- 【Android】Android 广播大全
- 推荐一个spring cloud 学习路线,绝对合理化
- linux下recv 、send阻塞、非阻塞区别和用法
- sql server与C#中的字符串相等等效写法
- SimpleDateFormat转换时间,12,24时间格式[转]
- 人工智能——Singleton模式
- js简单的面试题
- Python import搜索的路径顺序