【剑指Offer】数组中出现次数超过一半的数字 解题报告(Python)
2024-10-16 08:05:29
【剑指Offer】数组中出现次数超过一半的数字 解题报告(Python)
标签(空格分隔): 剑指Offer
题目地址:https://www.nowcoder.com/ta/coding-interviews
题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
解题方法
我们利用数组的特点,使用一个times保存当前数字出现了多少次。这样,如果出现了0次,把新数字加入res;如果当前数字和res相等,那么times+=1;如果不等times-=1。
最后遍历完成之后res保存的数字,应该是出现超过一半的数字或者没有出现超过一半的数字。因此,最后还是要判断一下,到底是不是出现超过了一半。
# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
if not numbers: return 0
res = 0
times = 0
for i, num in enumerate(numbers):
if times == 0:
res = num
times = 1
elif num == res:
times += 1
else:
times -= 1
return res if numbers.count(res) > len(numbers) / 2 else 0
方法二:
使用Counter类。
# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
if not numbers: return 0
count = Counter(numbers).most_common()
if count[0][1] > len(numbers) / 2:
return count[0][0]
return 0
Date
2018 年 3 月 21 日 – 做事细心点,最近有点困,要抵制困意
最新文章
- CSS3 animation 动画
- [ASP.NET MVC 小牛之路]18 - Web API
- 学习SpringMVC——从HelloWorld开始
- Java8闭包
- CreateCompatibleDC 与 CreateCompatibleBitmap 小小结
- Emit学习(2) - IL - 值类型和引用类型(补)
- java_easyui体系之DataGrid(3)[转]
- dedecms首页调用栏目内容和单页内容的方法
- php大力力 [005节] php大力力简单计算器001
- python3获取当前目录(转)
- http://www.mxchip.com/talk/news/jishuwenzhang/2014-09-11/67.html
- 将table内容输出为csv文件
- 竞价广告系统-ZooKeeper介绍
- linux中移动光标
- js 控制随机数生成概率
- MySQL 把两个结果集拼接到一起(两个结果集的列一模一样)
- django之Models和ORM
- TableView中Label自适应高度
- bzoj 3285 离散对数解指数方程
- jquery datables ajax分页后的点击事件无效是怎么回事
热门文章
- 日常Java 2021/10/10
- @FeignClient同一个name,多个配置类的解决方案
- 【Linux】【Services】【VersionControl】Git基础概念及使用
- spring mvc idea创建
- Springboot Oauth2 集成Swagger2权限验证实战
- js和jquery之间的转换
- Ajax异步更新网页(使用原生JavaScript)
- java配置文件的使用 —— 设置一个类为单例模式
- 35、搜索插入位置 | 算法(leetode,附思维导图 + 全部解法)300题
- tomcat架构分析及配置详解