python 计算数组中每个数字出现多少次--“Bucket”桶的思想
作者:七度上弦 发布时间:2023-06-28 19:37:55
标签:数组,数字,多少次
题目:
解法一:比较元素是否相等
思路说明:
这种应该是普通人最先想到的解法,先获取到数组之后进行有小到大排序,然后初始化一个min=0(代表新数字的开始角标),然后遍历新数组的每一个元素,如果两个元素不相等,count等于i-min,然后再把i赋值给min,当i遍历到最后一个元素时,count等于数组长度-min(这里的min是上一轮循环后最后一组数字的第一个元素的角标),当然这种解法面试官不会喜欢?
(m, n) = input().split()
ar = [int(x) for x in input().split()]
res = []
ar.sort()
min = 0
for i in range(1,len(ar)) :
if ar[i-1] != ar[i]:
count = i - min
min = i
res.append(str(count))
if i == (len(ar)-1):
count = len(ar)-min
res.append(str(count))
print(' '.join(res))
解法二:桶计算
思路:获取到输入的数组之后,获取该数组的长度,因为根据题目N<=20,也就是说数组的元素不会超过20,那么我们定义一个1维,长度为20的数组res,并初始化元素为0是足够的。先上代码,再进行解析
(m, n) = input().split()
ar = [int(x) for x in input().split()]
result = []
res = [0 for x in range(20)]
for a in ar:
res[a-1]+=1
for r in res:
if r != 0:
result.append(str(r))
print(' '.join(result))
以上的而核心代码就在于这两行
for a in ar:
res[a-1]+=1
我们遍历输入的数组ar的每一个元素,用res[a]的数值代表a出现的次数,我们每次循环,总能找到合适的桶存放a,那么我们直接+1即可,比如说ar = [2, 2, 1, 4]
循环1:
a = 2
res[2] = 0+1 = 1
循环2:
a = 2
res[2] = 1 +1 =2
循环3:
a = 1
res[1] = 0+1 = 1
循环4:
a = 4
res[4] = 0+1 = 1
这样我们得到的 res = [0, 1 ,2 ,0 ,1 ,0 ····]
延伸:桶排序
根据以上的思路我们得到了一个新的数组res,仔细分析这个数组的意思,1出现1次,2出现2次,4出现1次,因为数组的特性保证元素的角标是从小到大排序,这就衍生出了桶排序的概念,忽略0的情况,用两个循环,外层循环遍历len(res)次,角标为i,内层循环遍历res[i]次,角标为j,意思就是有几个输出几个,例如1有1个,那就输出1个,2有两个,就循环两次,输出两次,4有1个,就输出一个,扩展代码如下:
#省略上述代码
for i in range(len(res)):
if res[i] != 0:
for j in range(res[i]):
result.append(i)
print(result)
执行结果如下:
来源:http://blog.csdn.net/qq_14908027/article/details/78788085
0
投稿
猜你喜欢
- 如果要得到返回值,需要用Command的方法。 首先说明,返回值有两种。一种是在存储过程中直接return一个值,就象C和VB的函数返回值那
- 1、前言 MySQL 是完全网络化的跨平台关系型数据库系统,同时是具有客户机/服务器体系结构的分布式数据库管理系统。它具有功能强、使用简便、
- 作者: Terrance译者:Sheneyan(子乌)时间:2010.2.6英文原文:13 Useful WordPress SQL Que
- 有关JS中字符串的相关文章,现在网上大概不计其数了。这里我不想再就这个问题做过多的论述,只是对几种方式的实现在各种浏览器中的执行效率进行对比
- 类似于and操作类似于or操作# 类型转换# sortedli=[2,45,1,67,23,10]li.sort() #list的排序方法p
- --sql语句就用下面的存储过程 /*--数据导出Excel导出查询中的数据到Excel,包含字段名,文件为真正的Excel文件,如果文件不
- 月份转换到中文Function MonthToCH(TheMonth) Dim mm mm=split("一,
- 经过摸索和实践,我把自己的解决方法,写在下面: 说明: 我的Oracle客户端的版本是 oracle 9i, 安装client端的时候,不能
- 本文实例讲述了PHP判断密码强度的方法。分享给大家供大家参考,具体如下:一、php页面$score = 0;if(!empty($_GET[
- 我对这两种连接方式认识不够深,似乎朋友们对此也没有定论。请问哪一种更好呢?DSN是采用数据源的连接方式,其使用方法是: Conn.
- 本文是对pandas官方网站上《10Minutes to pandas》的一个简单的翻译,原文在这里。这篇文章是对pandas的一个简单的介
- gonews是基于 go+vue 实现的golang每日新闻浏览与检索平台项目地址: Github线上Demo:GoNews数据来源: Go
- 代码如下:'===================================== '转换内容,防止意外 '==
- 这是asp利用dictionary创建二维数组的例子,这样做的优点是:1、数组下标可以是字符串2、长度不是固定的<'% ’==
- 当来自应用程序的第一个连接控制锁而第二个连接需要相冲突的锁类型时,将发生阻塞。其结果是强制第二个连接等待,而在第一个连接上阻塞。不管是来自同
- 体系结构 Microsoft按照客户/服务器体系结构的分布进行操作。这种方法产生不必要的代价和复杂性。在Internet中,Oracle已经
- jquery有一个插件叫Timer,很有意思,咱来实现一个简版的yui3的node timer。但还是应当首先交代下yui3的node扩展的
- 加入CDC的这段日子里,工作中积累的小心得都密密麻麻的收在册子里。恰逢近期的校园招聘正如火如荼的展开着,借此机会,我把这一些不太成熟的小想法
- 前几天,为了增强本站的SEO,着手把另一个域名:www.aspxhome.com下的所有页面301转向到www.cidianwang.com
- def cndebug(obj=False): """ Author : Nemon Update : 200