python 計算數(shù)組中每個數(shù)字出現(xiàn)多少次--“Bucket”桶的思想

更新時間：2017年12月19日 23:48:22 作者：七度上弦

這篇文章主要介紹了python 計算數(shù)組中每個數(shù)字出現(xiàn)多少次--“Bucket”桶的思想,需要的朋友可以參考下

題目：

這里寫圖片描述

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

思路說明：

這種應該是普通人最先想到的解法，先獲取到數(shù)組之后進行有小到大排序，然后初始化一個min=0（代表新數(shù)字的開始角標），然后遍歷新數(shù)組的每一個元素，如果兩個元素不相等，count等于i-min，然后再把i賦值給min，當i遍歷到最后一個元素時，count等于數(shù)組長度-min（這里的min是上一輪循環(huán)后最后一組數(shù)字的第一個元素的角標），當然這種解法面試官不會喜歡？

(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))

解法二：桶計算

思路：獲取到輸入的數(shù)組之后，獲取該數(shù)組的長度，因為根據(jù)題目N<=20，也就是說數(shù)組的元素不會超過20，那么我們定義一個1維，長度為20的數(shù)組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

我們遍歷輸入的數(shù)組ar的每一個元素，用res[a]的數(shù)值代表a出現(xiàn)的次數(shù)，我們每次循環(huán)，總能找到合適的桶存放a，那么我們直接+1即可，比如說ar = [2, 2, 1, 4]

循環(huán)1： 
a = 2 
res[2] = 0+1 = 1 
循環(huán)2： 
a = 2 
res[2] = 1 +1 =2 
循環(huán)3： 
a = 1 
res[1] = 0+1 = 1 
循環(huán)4： 
a = 4 
res[4] = 0+1 = 1 
這樣我們得到的 res = [0, 1 ,2 ,0 ,1 ,0 ····]

延伸：桶排序

根據(jù)以上的思路我們得到了一個新的數(shù)組res，仔細分析這個數(shù)組的意思，1出現(xiàn)1次，2出現(xiàn)2次，4出現(xiàn)1次，因為數(shù)組的特性保證元素的角標是從小到大排序，這就衍生出了桶排序的概念，忽略0的情況，用兩個循環(huán)，外層循環(huán)遍歷len(res)次，角標為i，內層循環(huán)遍歷res[i]次，角標為j，意思就是有幾個輸出幾個，例如1有1個，那就輸出1個，2有兩個，就循環(huán)兩次，輸出兩次，4有1個，就輸出一個，擴展代碼如下：

#省略上述代碼
for i in range(len(res)):
  if res[i] != 0:
    for j in range(res[i]):
      result.append(i)
print(result)

執(zhí)行結果如下：

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python 計算數(shù)組中每個數(shù)字出現(xiàn)多少次--“Bucket”桶的思想

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具