python 计算数组中每个数字出现多少次--“Bucket”桶的思想

题目：

解法一：比较元素是否相等

思路说明：

这种应该是普通人最先想到的解法，先获取到数组之后进行有小到大排序，然后初始化一个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)

执行结果如下：

赞 (0)

相关推荐

  • Python实现1-9数组形成的结果为100的所有运算式的示例

    问题: 编写一个在1,2,-,9(顺序不能变)数字之间插入+或-或什么都不插入,使得计算结果总是100的程序,并输出所有的可能性.例如:1 + 2 + 34–5 + 67–8 + 9 = 100. from functools import reduce operator = { 1: '+', 2: '-', 0: '' } base = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] def isHundred(num): #转化为8位3进制数,得

  • Python语言描述连续子数组的最大和

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值

  • Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算.分享给大家供大家参考,具体如下: 说明:本人前段时间遇到的求n个数组的所有排列组合的问题,发现笛卡尔积算法可以解决,但是网上搜索的只有Java版本的实现,于是自己试着用python实现,由于新手代码不太规范. 代码:本人封装了一个类Cartesian(笛卡尔),其中封装了变量和方法: 1.变量 datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组 coun

  • Python实现二维数组按照某行或列排序的方法【numpy lexsort】

    本文实例讲述了Python实现二维数组按照某行或列排序的方法.分享给大家供大家参考,具体如下: lexsort支持对数组按指定行或列的顺序排序:是间接排序,lexsort不修改原数组,返回索引. (对应lexsort 一维数组的是argsort a.argsort()这么使用就可以:argsort也不修改原数组, 返回索引) 默认按最后一行元素有小到大排序, 返回最后一行元素排序后索引所在位置. 设数组a, 返回的索引ind,ind返回的是一维数组 对于一维数组, a[ind]就是排序后的数组.

  • Python实现返回数组中第i小元素的方法示例

    本文实例讲述了Python实现返回数组中第i小元素的方法.分享给大家供大家参考,具体如下: #! /usr/bin/env python #coding=utf-8 #期望为线性时间的选择算法 import random class RandomSelect(object): def Partition(self,a, p, r): x=a[r] i=p-1 for j in range(p, r): '''如果a[j]>x,则只需将j的值加1即可使循环不变量继续保持; 如果a[j]<=x,则

  • Python简单计算数组元素平均值的方法示例

    Python简单计算数组元素平均值的方法示例

    本文实例讲述了Python简单计算数组元素平均值的方法.分享给大家供大家参考,具体如下: Python 环境:Python 2.7.12 x64 IDE :     Wing IDE Professional  5.1.12-1 题目:  求数组元素的平均值 实现代码: # coding:utf-8 #求数组元素的平均值 a=[1,4,8,10,12] b=len(a) sum=0 print "我们测试结果:" print "数组长度为:",b for i in

  • Python创建二维数组实例(关于list的一个小坑)

    0.目录 1.遇到的问题 2.创建二维数组的办法 •3.1 直接创建法 •3.2 列表生成式法 •3.3 使用模块numpy创建 1.遇到的问题 今天写Python代码的时候遇到了一个大坑,差点就耽误我交作业了... 问题是这样的,我需要创建一个二维数组,如下: m = n = 3 test = [[0] * m] * n print("test =", test) 输出结果如下: test = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 是不是看起来没有一点问

  • Python算法输出1-9数组形成的结果为100的所有运算式

    问题: 编写一个在1,2,-,9(顺序不能变)数字之间插入+或-或什么都不插入,使得计算结果总是100的程序,并输出所有的可能性.例如:1 + 2 + 34–5 + 67–8 + 9 = 100. from functools import reduce operator = { 1: '+', 2: '-', 0: '' } base = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] def isHundred(num): #转化为8位3进制数,得

  • python 计算数组中每个数字出现多少次--“Bucket”桶的思想

    python 计算数组中每个数字出现多少次--“Bucket”桶的思想

    题目: 解法一:比较元素是否相等 思路说明: 这种应该是普通人最先想到的解法,先获取到数组之后进行有小到大排序,然后初始化一个min=0(代表新数字的开始角标),然后遍历新数组的每一个元素,如果两个元素不相等,count等于i-min,然后再把i赋值给min,当i遍历到最后一个元素时,count等于数组长度-min(这里的min是上一轮循环后最后一组数字的第一个元素的角标),当然这种解法面试官不会喜欢? (m, n) = input().split() ar = [int(x) for x in

  • python把数组中的数字每行打印3个并保存在文档中的方法

    如下所示: arrs=[2,15,48,4,5,6,7,6,4,1,2,3,6,6,7,4,6,8] f=open('test.txt','w+') count=0 for temp in arrs: count+=1 print >> f,temp, if(count%3==0): print >> f f.close() 结果: 以上这篇python把数组中的数字每行打印3个并保存在文档中的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • Python查找数组中数值和下标相等的元素示例【二分查找】

    本文实例讲述了Python查找数组中数值和下标相等的元素.分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的.请编程实现一个函数,找出数组中任意一个数值等于其下标的元素,例如在数组[-3,-1,1,3,5]中,3和他的下标相等. 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标.如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找. 算法示例: # -*-

  • Python划分数组为连续数字集合的练习

    目录 1.问题描述 2.解决方案 3.结语 本文转自微信公众号:"算法与编程之美" 1.问题描述 给你一个整数数组 nums 和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合. 如果可以,请返回 True:否则,返回 False. 示例 1: 输入:nums = [1,2,3,3,4,4,5,6], k = 4 输出:true 解释:数组可以分成 [1,2,3,4] 和 [3,4,5,6]. 示例 2: 输入:nums = [3,2,1,2,3,4,3

  • Java C++解决在排序数组中查找数字出现次数问题

    Java C++解决在排序数组中查找数字出现次数问题

    目录 1.题目 2.思路 3.c++代码 4.java代码 1.题目 统计一个数字在排序数组中出现的次数. 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 提示: 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组 -10^9 <= target &l

  • js求数组中全部数字可拼接出的最大整数示例代码

    前言 最近在工作碰到一个问题,就是用javascript求数组中所有数字能拼接出的最大整数,数组的每一项为单独的拼接项,不能再拆开,例如[2,34]中2和34分别为要被拼接的数字,而不是说34还能继续拆分为3和4. 具体需求为,将[7,321,35,4]拼接为7435321.下面话不多说了,来一起看看详细的实现方法吧. 我设计的算法如下: function insertSort(arr) { let res = [arr[0]]; for (let i = 1, len = arr.length

  • 对python numpy数组中冒号的使用方法详解

    python中冒号实际上有两个意思:1.默认全部选择:2. 指定范围. 下面看例子 定义数组 X=array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19,20]]) 输出为5x4二维数组 第一种意思,默认全部选择: 如,X[:,0]就是取矩阵X的所有行的第0列的元素,X[:,1] 就是取所有行的第1列的元素 第二种意思,指定范围,注意这里含左不含右 如,X[:, m:n]即取矩阵X的所有行中的的第m到n-1列数据,含左不含右

  • js根据需要计算数组中重复出现某个元素的个数

    一.有时候的根据需要需要计算数组中某个元素重复出现的个数 var arr = ["apple","orange","apple","orange","pear","orange"]; 计算出来重复出现的元素个数:{apple: 2, orange: 3, pear: 1} 二.代码实现 //统计一个数组中有多少个不重复的单词: // 不用reduce时: var arr = ["

  • c#实现从字符串数组中把数字的元素找出来

    下面这个字符串数组: string[] str = { "3","y","34","QQ","41","adsf4","7","52"}; 实现这个要求的方法也许会很多.下面Insus.NET使用一个通用的方法来实现: 面向对象,创建一个类别Class Digit: class Digit { private int _D; public int

  • python 将字符串中的数字相加求和的实现

    python 将字符串中的数字相加求和的实现

    计算字符串中所有数字的和,字符串中有数字和字母组合而成 如果出现连续数字,按照一个数操作 具体解释在代码行里: def sum_str(str1): len1=len(str1) #首先将字符串str1的长度赋值给len1 sum = n = 0 #建立一个值为0的空变量sun #建立一个值为0的空变量n for i in range(len1): #用i来遍历字符串的长度 if 49 <= ord(str1[i]) <= 57: #判断字符ascii码是否在数字ascii值范围内 n = n

随机推荐